Subversion Repositories planix.SVN

#include "os.h"

#include <mp.h>

#include <libsec.h>

// Gordon's algorithm for generating a strong prime

//	Menezes et al () Handbook, p.150

void

genstrongprime(mpint *p, int n, int accuracy)

{

	mpint *s, *t, *r, *i;

	if(n < 64)

		n = 64;

	s = mpnew(n/2);

	genprime(s, (n/2)-16, accuracy);

	t = mpnew(n/2);

	genprime(t, n-mpsignif(s)-32, accuracy);

	// first r = 2it + 1 that's prime

	i = mpnew(16);

	r = mpnew(0);

	itomp(0x8000, i);

	mpleft(t, 1, t);	// 2t

	mpmul(i, t, r);		// 2it

	mpadd(r, mpone, r);	// 2it + 1

	for(;;){

		if(probably_prime(r, 18))

			break;

		mpadd(r, t, r);	// r += 2t

	}

	// p0 = 2(s**(r-2) mod r)s - 1

	itomp(2, p);

	mpsub(r, p, p);

	mpexp(s, p, r, p);

	mpmul(s, p, p);

	mpleft(p, 1, p);

	mpsub(p, mpone, p);

	// first p = p0 + 2irs that's prime

	itomp(0x8000, i);

	mpleft(r, 1, r);	// 2r

	mpmul(r, s, r);		// 2rs

	mpmul(r, i, i);		// 2irs

	mpadd(p, i, p);		// p0 + 2irs

	for(;;){

		if(probably_prime(p, accuracy))

			break;

		mpadd(p, r, p); // p += 2rs

	}

	mpfree(i);

	mpfree(s);

	mpfree(r);

	mpfree(t);

}