Wheel factorization: Efficient? - Page 13

3.14159 · 2010-07-19, 22:54

Quote:

That's an RNG, not a PRNG. (That site actually calls them TRNGs, a synonym for RNGs.)

I wished to examine whether or not there was any observable difference between random.org and PARI's random(n) function.

CRGreathouse · 2010-07-19, 22:59

Quote:

Originally Posted by 3.14159

I wished to examine whether or not there was any observable difference between random.org and PARI's random(n) function.

If you look at the link I gave when I explained how Pari generates random numbers, you'll see there's a description of the battery of tests passed by it (e.g., Crush). This is a better comparison then you'd be able to throw together in a few minutes (or days!).

3.14159 · 2010-07-19, 23:03

Quote:

If you look at the link I gave when I explained how Pari generates random numbers, you'll see there's a description of the battery of tests passed by it. This is a better comparison then you'd be able to throw together in a few minutes (or days!).

http://wims.unice.fr/wims/, I think, uses PARI for its computations.

Its warning on the random primes generator:
Warning: It is strongly discouraged to use this tool for the need of cryptology in real situations. Primes having travelled through the Internet have no confidentiality.

Quote:

Primes having travelled through the Internet have no confidentiality.

Which is why they are to be proven prime first.

P.S: Congrats on having a prime-numbered- No wait, that's 17 * 61..

CRGreathouse · 2010-07-19, 23:07

Strictly, that's not relevant here: that speaks to the possibility of a side-channel attack (reading the numbers as they're passed through TCP) rather than the weakness of the PRNG itself. But the same warning (with different reasoning) could be applied to the PRNG since it's not designed to be cryptographically secure.

Quote:

Originally Posted by 3.14159

Which is why they are to be proven prime first.

Huh? The problem is that someone can read them, not that they're wrong. But sure, prove primality if you like.

Actually, for practical cryptographic algorithms, primality is almost never proven -- random tests like Miller-Rabin are used instead.

3.14159 · 2010-07-19, 23:09

Quote:

Strictly, that's not relevant here: that speaks to the possibility of a side-channel attack.

Ah. The non-math attacks. (Ex: Timing attack)

Easier than the math-based attacks (Impossible to do.)

Quote:

Actually, for practical cryptographic algorithms, primality is almost never proven -- random tests like Miller-Rabin are used instead.

Don't you mean, PRP tests?

CRGreathouse · 2010-07-19, 23:24

Quote:

Originally Posted by 3.14159

Don't you mean, PRP tests?

Random was what I meant, but I could have said PrP tests or compositeness tests had I desired.

3.14159 · 2010-07-19, 23:38

@CRG: Do you know a simple program that can be written to check for an SPRP pseudoprime list for bases 2, 3, and 5?

CRGreathouse · 2010-07-20, 00:25

Quote:

Originally Posted by 3.14159

@CRG: Do you know a simple program that can be written to check for an SPRP pseudoprime list for bases 2, 3, and 5?

I posted one not long ago -- search for isSPRP.

xilman · 2010-07-20, 04:14

Quote:

Originally Posted by 3.14159

How would they be "predictable"? How does one suddenly become a crystal ball?

Read up about the famous Netscape attack and the like. I know you don't like Wikipedia references so you should go directly to its referenced sources.

Quote:

Originally Posted by 3.14159

And, the risk of an attacker actually succeeding is minimal, as most people are idiots when it comes to computers. (Unfortunately, that set of people includes me.)

Unfortunately (or should that be fortunately?) not everyone is an idiot like you. It only takes one competent person to implement an attack and then idiots can use that implementation to succeed with high probability.

Paul

xilman · 2010-07-20, 04:20

Quote:

Originally Posted by 3.14159

http://wims.unice.fr/wims/, I think, uses PARI for its computations.

Its warning on the random primes generator:
Warning: It is strongly discouraged to use this tool for the need of cryptology in real situations. Primes having travelled through the Internet have no confidentiality.

Which is why they are to be proven prime first.

No! Your bold-faced statement is completely wrong.

To see why, assume that the generator proves its output is prime before it is sent to you. The point of the warning is that, in principle, anyone between the generator and you can read and record the primes which you receive. After that it's game over.

Paul

3.14159 · 2010-07-20, 11:58

Quote:

Unfortunately (or should that be fortunately?) not everyone is an idiot like you. It only takes one competent person to implement an attack and then idiots can use that implementation to succeed with high probability.

Didn't have to insult me that badly. :|

Quote:

To see why, assume that the generator proves its output is prime before it is sent to you. The point of the warning is that, in principle, anyone between the generator and you can read and record the primes which you receive. After that it's game over.

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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Wheel Factorization	a1call	Factoring	11	2017-06-19 14:04
Efficient Test	paulunderwood	Computer Science & Computational Number Theory	5	2017-06-09 14:02
LL tests more credit-efficient than P-1?	ixfd64	Software	3	2011-02-20 16:24
A Wheel	storm5510	Puzzles	7	2010-06-25 10:29
Most efficient way to LL	hj47	Software	11	2009-01-29 00:45

2010-07-19, 23:38	#139
3.14159 May 2010 Prime hunting commission. 2⁴×3×5×7 Posts	@CRG: Do you know a simple program that can be written to check for an SPRP pseudoprime list for bases 2, 3, and 5?