Blog literacki, portal erotyczny - seks i humor nie z tej ziemi
/*
Author: Pate Williams (c) 1997
Maurer's algorithm for generating provable primes.
See "Handbook of Applied Cryptography" by Alfred J.
Menezes et al page 153.
*/
#include
#include
#include
#include
#include "lip.h"
long OddRandom(long bit_length)
{
long i, mask = 1, n;
bit_length--;
for (i = 1; i <= bit_length; i++)
mask |= 1 << i;
if (bit_length < 16)
n = rand();
else
n = (rand() << 16) | rand();
n |= 1 << bit_length;
n &= mask;
if ((n & 1) == 0) n++;
return n;
}
void PROVABLE_PRIME(long k, verylong *zn)
{
double c, r, s;
int success;
long B, m, n, p, sqrtn;
verylong zI = 0, zR = 0, za = 0, zb = 0, zc = 0;
verylong zd = 0, zk = 0, zl = 0, zq = 0, zu = 0;
srand(time(NULL));
zrstarts(time(NULL));
if (k <= 20) {
do {
n = OddRandom(k);
sqrtn = sqrt(n);
zpstart2();
do p = zpnext(); while (n % p != 0 && p < sqrtn);
} while (p < sqrtn);
zintoz(n, zn);
}
else {
c = 0.1;
m = 20;
B = c * k * k;
if (k > 2 * m)
do {
s = rand() / (double) RAND_MAX;
r = pow(2.0, s - 1.0);
} while (k - r * k <= m);
else
r = 0.5;
PROVABLE_PRIME(r * k + 1, &zq);
zone(&za);
zlshift(za, k - 1, &zk);
zcopy(zq, &za);
zlshift(za, 1l, &zl);
zdiv(zk, zl, &zI, &za);
zsadd(zI, 1l, &zl);
zlshift(zI, 1l, &zu);
success = 0;
while (!success) {
do zrandomb(zu, &zR); while (zcompare(zR, zl) < 0);
zmul(zR, zq, &za);
zlshift(za, 1l, &zb);
zsadd(zb, 1l, zn);
zcopy(zR, &za);
zlshift(za, 1l, &zR);
zpstart2();
p = zpnext();
while (zsmod(*zn, p) != 0 && p < B) p = zpnext();
if (p >= B) {
zcopy(*zn, &zc);
zsadd(zc, - 2l, &zb);
do
zrandomb(*zn, &za);
while (zscompare(za, 2l) < 0 || zcompare(za, zb) > 0);
zsadd(*zn, - 1l, &zc);
zexpmod(za, zc, *zn, &zb);
if (zscompare(zb, 1l) == 0) {
zexpmod(za, zR, *zn, &zb);
zcopy(zb, &zd);
zsadd(zd, - 1l, &zb);
zgcd(zb, *zn, &zd);
success = zscompare(zd, 1l) == 0;
}
}
}
}
zfree(&zI);
zfree(&zR);
zfree(&za);
zfree(&zb);
zfree(&zc);
zfree(&zd);
zfree(&zk);
zfree(&zl);
zfree(&zq);
zfree(&zu);
}
int main(void)
{
long k;
verylong zn = 0;
for (k = 10; k <= 55; k += 5) {
PROVABLE_PRIME(k, &zn);
printf("%ld %ld %ld ", k, z2log(zn), zprobprime(zn, 5));
zwriteln(zn);
}
zfree(&zn);
return 0;
}