mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-09-08, 16:58   #12
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72×47 Posts
Default

Isn’t the format of the composite a factor?
Is the computing cost of similar sized Fermat-numbers, Mersenne-numbers and general-format-numbers the same?
Are the available tools/methods for different formats of composites the same?

Last fiddled with by a1call on 2022-09-08 at 17:08
a1call is online now   Reply With Quote
Old 2022-09-08, 20:29   #13
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2×3×52×37 Posts
Default

Quote:
Originally Posted by a1call View Post
Isn’t the format of the composite a factor?
Is the computing cost of similar sized Fermat-numbers, Mersenne-numbers and general-format-numbers the same?
Are the available tools/methods for different formats of composites the same?
OP used "RSA" and "random integer" in his query. All the replies were for those generic items.

No, special numbers are not the same difficulty as general numbers. If you care to know more, look up "special number field sieve" and "general number field sieve" on wiki. These are the SNFS and GNFS referred so often in this subforum.

Yes, the tools to factor are the same, if by tools/methods you mean software packages. CADO-NFS and Yafu/GGNFS/msieve both solve both types of input numbers.
VBCurtis is offline   Reply With Quote
Old 2022-09-08, 21:03   #14
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

72·47 Posts
Default

Yes, I meant software. I appreciate the info. Thank you.
a1call is online now   Reply With Quote
Old 2022-09-30, 09:12   #15
Unitome
 
Unitome's Avatar
 
Apr 2021
Hoarding Knowledge

101002 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
OP used "RSA" and "random integer" in his query. All the replies were for those generic items.

No, special numbers are not the same difficulty as general numbers. If you care to know more, look up "special number field sieve" and "general number field sieve" on wiki. These are the SNFS and GNFS referred so often in this subforum.

Yes, the tools to factor are the same, if by tools/methods you mean software packages. CADO-NFS and Yafu/GGNFS/msieve both solve both types of input numbers.
Can you know if something is special without a. making the number yourself according to a formula, or b. trying to factor it? What are the chances of randomly encountering a special number at say 100-150 digit length? I know semistrong semiprimes are about 1 in 300 random numbers at 150 digit length levels.

One good thing about searching for semiprimes at large number levels, is that the byproduct is you find a lot of large primes. These primes could be kept secret (primes are of no value to the network, only semiprimes) when you do find them, and use them to make your own RSA encryption. Of course if you were just looking for large primes you could do it faster than looking for semiprimes, but still you do get a useful byproduct from mining, which is neat.

Last fiddled with by Unitome on 2022-09-30 at 09:26
Unitome is offline   Reply With Quote
Old 2022-09-30, 10:14   #16
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3·5·683 Posts
Default

You may do GCD with a lot of SNFS-able known forms. You have a very slim chance that your number or a multiple of it comes out as the GCD, and then you know it is SNFS-able. About the same chance like in shooting the Moon with a bow/an arrow or slingshot/stone. This is (coarse) how Yafu and other tools determine if the number comes from a special form or not, and they have to do SNFS or GNFS on the number. For few-hundred-digits numbers, this process is very fast (only takes seconds/minutes).

You also have some chance (like shooting the thirteenth ring of Saturn with the same arrow or stone ) that the GCD comes out with a proper factor, and then you factored your number without needing any NFS.

Last fiddled with by LaurV on 2022-09-30 at 10:17
LaurV is offline   Reply With Quote
Old 2022-09-30, 12:36   #17
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×52×71 Posts
Default

Paul Zimmermann showed that for cryptosystems based on discrete logarithms you can select a prime modulus that makes NFS for discrete logarithms much easier than one would expect based on the size of the modulus.

So to answer a previous question, if you can recognize numbers for which SNFS is feasible you can build RSA keys that have a trapdoor even if you don't know the factorization of the modulus.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why integer factorization is in P/FP? tetramur Factoring 4 2019-01-23 20:51
Integer factorization? bearnol2 Information & Answers 7 2010-12-09 02:50
Integer factorization with q < 2p mgb Math 36 2009-11-07 15:59
Integer Factorization mgb Math 16 2007-12-17 10:43
Integer Factorization 2 mgb Math 5 2007-07-23 12:55

All times are UTC. The time now is 15:54.


Tue Nov 29 15:54:13 UTC 2022 up 103 days, 13:22, 1 user, load averages: 0.58, 0.84, 0.92

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.

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