Testing a list of 65-digit primes instead of one at a time - Page 3

Dr Sardonicus · 2022-06-10, 14:07

Quote:

Originally Posted by xilman

Arjen Lenstra et al. did something closely similar to this exercise a few years back.

They collected a very large number of RSA public moduli and found common factors within the set, thereby breaking a large number of live public keys.

I will see if I can find the paper ... here it is https://eprint.iacr.org/2012/064

https://souravsengupta.com/publications/2017_iciss.pdf indicates that the algorithm can be parallelized.

I found this long-ago thread about this sort of thing...

ThiloHarich · 2022-06-14, 13:10

Daniel Bernstein covered this Problem in the Remainder- and Product Trees:

https://cr.yp.to/arith/scaledmod-20040820.pdf

Using Fast (n*log(n)) Multiplications, you can find the gcd of a number and some other numbers (possible divisors) fast, by using a tree.
This can also be used in the Quadratic Sieve.

MattcAnderson · 2022-06-18, 06:14

see post number 12 from kar_bon.

That is a good post.

Easy solution to OP's request.

That is all.

Matt

Have a nice day.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
PRP double checks are also included in the first time list	retina	PrimeNet	6	2017-10-29 01:31
Manual testing on CPU list	Fred	PrimeNet	3	2016-02-12 02:49
Time needed to factor a 150 digit number	ladderbook	Factoring	14	2008-11-27 13:02
Is it time for a 100M digit option?	petrw1	PrimeNet	60	2008-09-30 22:43
50 Digit Testing	wblipp	ElevenSmooth	1	2003-11-15 23:53

2022-06-14, 13:10	#24
ThiloHarich Nov 2005 104₁₀ Posts	Daniel Bernstein covered this Problem in the Remainder- and Product Trees: https://cr.yp.to/arith/scaledmod-20040820.pdf Using Fast (n*log(n)) Multiplications, you can find the gcd of a number and some other numbers (possible divisors) fast, by using a tree. This can also be used in the Quadratic Sieve.

2022-06-18, 06:14	#25
MattcAnderson "Matthew Anderson" Dec 2010 Oregon, USA 2²×3×5×19 Posts	see post number 12 from kar_bon. That is a good post. Easy solution to OP's request. That is all. Matt Have a nice day.