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×5×11×53 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

10410 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

22×3×5×19 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
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 12:43.


Thu Jun 30 12:43:01 UTC 2022 up 77 days, 10:44, 0 users, load averages: 1.57, 1.44, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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