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

[Dr Sardonicus]

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]

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]

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.

[raresaturn]

Originally Posted by mathwiz

2. You are given a list of a hundred 65-digit primes

does such a list exist?

[chris2be8]

Originally Posted by raresaturn

does such a list exist?

http://factordb.com/listtype.php?t=4...ge=100&start=0

[Allen]

Originally Posted by Ombrah

"I'll give you 100 primes that it could be. How fast can you find it?"

Without programming, (assuming both primes are in the list as the OP suggested in the follow-up post, and also implying the C130 is not a perfect square), it's possible to solve this with pencil and paper by working modulo for some small . It may not be fast, but it can be done.

Using the example below:
For , this is not helpful since the C130 residues (mod 10) are all in the set ,
For , many the possible P65 values are eliminated, but not enough to justify the extra work.
For only 5 possible pairs remain when checking ≡ 249 (mod 10³)

71 *919 ≡ 249
119 *271 ≡ 249
261 *909 ≡ 249
279 *431 ≡ 249
289 *641 ≡ 249

At , only 1 pair in the list ≡ 6249 (mod 10⁴)

So you would only have to work out which of the 5 pairs from are ≡ 6249 (mod 10⁴).
0909 *1261 ≡ 6249

Example:
given C130= 1357133365099128468636613472790822406061039939164715664043583411268841764481114735848438228584847894580295360400816116941769956249

and random candidate list (sorted by last few digits for readability):

38491394993314292148096174014199642475797651712689733637646771007
38285878348587114141379798675052160022585777179593075633786996029
48619724008940493479020261101688656844488143667157941723357046039
52162655085588104739977263585328603229648182242504205495250318071
47747897607371660686341428144195187347042425066486227868100818087
39679655230048823471039104774228260320034353617900688180479653089
31827674851141125198901934152127926790542231684688718789698688119
36179205396315238299751754330597737063402006908324511390936773151
28482041848688669517832774499028728863775498585587311515451416159
30261430029840966165933966356550020617906093923370766114899641169
41917941719413724578029112735683555591086711577537070930622101199
28888324667017453435976355263280980939477297842782420649823252203
36563838741035740868291057593925959234731249807617810884147551203
28693136191668943409011221385950947593334498648458106520701352209
43176993310360421192793384761673076167661307908944868122466162229
45738127290058561414332460949657406700769472455055405036262280231
50221066529936804330693802101729850442106508598722754154408894237
33237820335095164018211982605668168770605838733367630165058541261
52298832782068940888574137140988199022916045260820728816039461271
48350695104739979924813599104203289208928943510883647320257204277
46031759748418444259903989352700710260511450885579159557877096279
37016898745919909020416907606027165055286191029262723560531701289
31650662967325689508991747014922699827427697004508512418296954361
41328526508775145408663618838585803163804359438824075537060332369
29035806460373287983729526227059590684551582398869468894088754403
49317945817979249202828158034236872503766663718226899939149506427
48091935683074738954383750529102908569554245882058330718041869431
51597455811618782295828988737617961728806093129630445507232302449
48590541915157460310520088026370572857002018568683863618663736467
41690146356121381286318791164988357036130503113939491720272706467
37148778664248597977127240956879918933117504836737581848483881539
33634812168003337728674103661438229102040853551993694874879585543
38283213103426717734959426715812111227299956559630113162999384569
47604892849638330745052459641485845280877890535333407457243853593
41248983749696394046865132432271516699377925250823991165539846599
48368215268674377845933945630695287366954837661717962357506115601
32386199648573227920708378858551544667861319269096559172525067627
31808708162198521015294326920791221444167960114416104494602286633
44134653513874465017537317055311121872868708517748690492212103641
40245937736774323055970724973945748879260214121952984362785870647
36769748647797317201322486127036640929536061651911210700757353651
36099194043913612751349967285291001641034605160235259636964297671
50834890520369498942435388574084857050319638792942600331403951717
45393583539598713052508238166909748345558729271005471259512965739
32124068605583945941546472335589087674438232320937755867687891739
50060886168187196756604566423192929179458838995251683813317928751
52022257262222812521811172896231682602135031395408081071190534759
38322126785385831287280309692368551263434978018802352159206031799
34743690340947337736333515703252030413001249422599851727554698819
38494215191193380613948040136491974396978274813265492912114529821
47064392133917762010372395295774125172757445633297478611497602829
28162112296107081456145036995298215661916004145878941545512246829
30898169039040977836999520453024275537090690319615600974127089831
40446823015791195119075580023122591895869781581235178881789566831
31010981582491379703816654144379869131691452806276998704173720837
37346312074476058765252835314949572632982493914660278940454400839
36306205129687060258037174921842490783200616758745303723793147859
45777439927117936082276872863137479451128066998369982829470090871
42479950313446467201597829512923507315180501571546188423257092893
40830997683267392474443062635732893271729319828011179211078950909
31450227100095961830002543700079233423897658506382181487801195917
52368725472255583382221418225385787781759831641364197435653303919
52444644169719682038189505191760962458792517492055976306073359923
46363063974011351173280738144219163973512936215578883414280342983
29022975894287667119686558174055407052081301691362553192752578993

[Allen]

Also in the "possible but not practical" tedious category, you could speed up the "manual approach" by taking the sum of the (decimal) digits (SOD) of C130. Since in the example, the SOD(C130) = 4, only 359 checks need to be performed. Way faster than the naive 65 choose 2 = 2080.

The SOD of primes and SOD(p*q) of for will never be (0,3,6,9), so there are only 6 possibilities to check.

Among the 65 "example" primes:

for SOD(x) == 1 there are 12 items
for SOD(x) == 2 there are 5 items
for SOD(x) == 4 there are 14 items
for SOD(x) == 5 there are 9 items
for SOD(x) == 7 there are 11 items
for SOD(x) == 8 there are 14 items

of these, only 4 combinations can make SOD(SOD(p)*SOD(q)) == 4:

a b count
1 4 12*14 = 168
2 2 5 choose 2= 10
5 8 9*14=126
7 7 11 choose 2= 55
==========
total 359 checks
(Still have to calculate 4289-414= 3875 additions modulo 10, not including the 414 occurrences of '0')