Wheel factorization: Efficient?

[CRGreathouse]

Originally Posted by 3.14159

How about if you generate via PARI? Is it equally weak as the internet generator?

I don't know of an attack on that particular implementation, but it's a linear feedback shift register, which has known vulnerabilities (e.g., the Berlekamp-Massey algorithm).

[retina]

Originally Posted by 3.14159

How about if you generate via PARI? Is it equally weak as the internet generator?

LFSRs are not cryptographically secure. Simple as that. If you want the primes for crypto work then the entire generating chain must be cryptographically secure. No shortcuts allowed. But the devil is in the details. Making good crypto is very hard. I suggest you buy a few books, I recommend this one: Bruce Schneier's "Practical Cryptography".

[3.14159]

But the devil is in the details. Making good crypto is very hard. I suggest you buy a few books, I recommend this one: Bruce Schneier's "Practical Cryptography".

.. Alternatively, an Internet search + Some reading on the subject via the internet.

[CRGreathouse]

Originally Posted by 3.14159

.. Alternatively, an Internet search + Some reading on the subject via the internet.

That will suffice to tell you the details, but I hope you don't write a cryptosystem on that basis!

[R.D. Silverman]

Originally Posted by CRGreathouse

I don't know of an attack on that particular implementation, but it's a linear feedback shift register, which has known vulnerabilities (e.g., the Berlekamp-Massey algorithm).

If speed is not a requirement, then use BBS.

[CRGreathouse]

Originally Posted by R.D. Silverman

If speed is not a requirement, then use BBS.

You mean instead of a LFSR? Yes, Blum Blum Shub is much more suitable to crypto (i.e., actually has value).

[jasonp]

There are many ways to build a cryptographically secure random number generator, assuming you have a good cryptographic primitive and a source that can supply sufficient entropy to seed it every so often. See NIST Special Publication 800-90 here. There's also been a lot of research into building a good entropy source when all you have is software, this is an excellent introduction.

[3.14159]

That will suffice to tell you the details, but I hope you don't write a cryptosystem on that basis!

Here's a bunny with a pancake on its head:

[3.14159]

Now that I know a bit of PARI, maybe I should attempt coding my test methods?

[CRGreathouse]

Sure, go for it.

[3.14159]

Alright: Here we go:

It works:

isSPRP(n,b=2) = {
forprime(p=2, nextprime(10^6),
if(n%p==0,return(p))
);
my(s=valuation(n-1,2),d=n>>s);
n = Mod(b, n)^d;
if (n == 1, return(n));
while(s--,
if (n == -1, return(n));
n = n^2;
);
n == -1
};

Timings:
For a composite that passes the trial division: 16 ms.