mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2022-06-10, 14:07   #23
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·11·283 Posts
Default

Quote:
Originally Posted by xilman View Post
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...
Dr Sardonicus is offline   Reply With Quote
Old 2022-06-14, 13:10   #24
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

22·33 Posts
Default

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.
ThiloHarich is offline   Reply With Quote
Old 2022-06-18, 06:14   #25
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

119210 Posts
Smile

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.
MattcAnderson is offline   Reply With Quote
Old 2022-11-28, 11:45   #26
raresaturn
 
raresaturn's Avatar
 
Jul 2021

2×19 Posts
Default

Quote:
Originally Posted by mathwiz View Post
2. You are given a list of a hundred 65-digit primes
does such a list exist?
raresaturn is offline   Reply With Quote
Old 2022-11-28, 16:20   #27
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2×1,213 Posts
Default

Quote:
Originally Posted by raresaturn View Post
does such a list exist?
http://factordb.com/listtype.php?t=4...ge=100&start=0
chris2be8 is offline   Reply With Quote
Old 2022-12-24, 16:13   #28
Allen
 
Dec 2022

2 Posts
Default a method to test by hand

Quote:
Originally Posted by Ombrah View Post
"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 10^x for some small x. It may not be fast, but it can be done.

Using the example below:
For x=1, this is not helpful since the C130 residues (mod 10) are all in the set \{1,3,7,9\},
For x=2, many the possible P65 values are eliminated, but not enough to justify the extra work.
For x=3 only 5 possible pairs remain when checking ≡ 249 (mod 103)
71 *919 ≡ 249
119 *271 ≡ 249
261 *909 ≡ 249
279 *431 ≡ 249
289 *641 ≡ 249
At x=4, only 1 pair in the list ≡ 6249 (mod 104)

So you would only have to work out which of the 5 pairs from x=1 are ≡ 6249 (mod 104).
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 is offline   Reply With Quote
Old 2022-12-24, 19:27   #29
Allen
 
Dec 2022

210 Posts
Default sum of digits approach

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 p,q > 3 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')
Allen is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:43.


Sun Feb 5 08:43:10 UTC 2023 up 171 days, 6:11, 1 user, load averages: 1.31, 1.02, 0.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔