20220908, 16:58  #12 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7^{2}×47 Posts 
Isn’t the format of the composite a factor?
Is the computing cost of similar sized Fermatnumbers, Mersennenumbers and generalformatnumbers the same? Are the available tools/methods for different formats of composites the same? Last fiddled with by a1call on 20220908 at 17:08 
20220908, 20:29  #13  
"Curtis"
Feb 2005
Riverside, CA
2×3×5^{2}×37 Posts 
Quote:
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. CADONFS and Yafu/GGNFS/msieve both solve both types of input numbers. 

20220908, 21:03  #14 
"Rashid Naimi"
Oct 2015
Remote to Here/There
7^{2}·47 Posts 
Yes, I meant software. I appreciate the info. Thank you.

20220930, 09:12  #15  
Apr 2021
Hoarding Knowledge
10100_{2} Posts 
Quote:
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 20220930 at 09:26 

20220930, 10:14  #16 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·5·683 Posts 
You may do GCD with a lot of SNFSable 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 SNFSable. 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 fewhundreddigits 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 20220930 at 10:17 
20220930, 12:36  #17 
Tribal Bullet
Oct 2004
2×5^{2}×71 Posts 
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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why integer factorization is in P/FP?  tetramur  Factoring  4  20190123 20:51 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
Integer factorization with q < 2p  mgb  Math  36  20091107 15:59 
Integer Factorization  mgb  Math  16  20071217 10:43 
Integer Factorization 2  mgb  Math  5  20070723 12:55 