20221023, 14:30  #1 
Aug 2019
2×3 Posts 
Factoring 1  25 bit numbers
Hello there. Attached is PARIGP code without any modular tricks, just a very basic bare bones factoring method.
It will probably factor up to 32bit semiprime numbers at a push, but the number of for loop cycles aren't perhaps the best that could be chosen. Also, the nested for loops aren't great. The 'e' stands for error. C is number to be factored, which it takes as its only input. It will happily factor anything up to 25 bits. I wish I was a better programmer, because then this 25bits could probably be extended to at least 5075 using modular arithmetic, but it takes time to learn. Thanks for reading. Have a nice day. 
20221023, 17:00  #2 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
10110110010100_{2} Posts 
25 bits is so small that factoring can be done in practice in constant time by table look up.
A 32M entry lookup table really isn't very fearsome any more. 
20221023, 19:48  #3 
Nov 2005
2^{2}×3^{3} Posts 
How will a 32 MB entry table look like?
A lookup table indicating if a odd number below 2^25 is composite would be around 2^(251) bit = 2^(25  1 3) byte ~ 2 GB. A (second or clever) table to one factor of the composite number might be even bigger. With the help of https://en.wikipedia.org/wiki/Wheel_factorization this might be reduced. I did not fully understand the code, but the main 'm' loop reminds me on : http://wrap.warwick.ac.uk/54707/1/WR...712000146a.pdf The Hart Factoring is simple and fast (n^1/3 compared to n^(1/2) by trial division). Last fiddled with by ThiloHarich on 20221023 at 20:27 
20221024, 02:01  #4 
Jun 2003
1010100111110_{2} Posts 

20221024, 15:36  #5 
Sep 2009
2^{2}·607 Posts 
What does that do that echo 'factor($n,10^5)'  gp fq doesn't? (That's assuming the number to factor is in $n and will find factors up to 10^5, though factor will work fast enough up to 10^7 before it's worth switching to ECM.)

20221024, 18:09  #6 
Aug 2019
2×3 Posts 
Update
The code has been updated. A lot of it is commented out atm, although it works it's not really been optimised very well. The original file had a mistake in it as well, where the multiplier m wasn't left in. I corrected that and made some improvements. It's not very well optimised for low numbers of decimal digits say less than five.
But it will now mostly factor up to 20 decimal digits fairly reliably. It maxes out at about 22 decimal digits, roughly 72 bits. For example, it factored 4,471,739,865,551,691,763 in just over two minutes. I think the limit in its present form is about 25 digits. But these are all (evenish  meaning rougly same lengths of factors in terms of digits) semiprimes, usually with 10 digits each max. It should still work with larger total lengths provided one factor is ten (decimal) digits or less. But there is a lot of theory involved behind the code, when I get time I shall probably write a paper that goes into some detail. I appreciate all feedback. Thanks for reading. Btw: No doubt somewhat preaching to the converted, but this is a handy resource for quickly generating semiprimes of various sizes: https://asecuritysite.com/encryption/random3?val=32 Last fiddled with by Jombo G on 20221024 at 18:10 
20221024, 19:06  #7  
"Oliver"
Sep 2017
Porta Westfalica, DE
17×79 Posts 
You might want to have a look at http://www.alpertron.com.ar/ECM.HTM, which states that it factors the number you mentioned in "0.0s":
Quote:


20221024, 19:20  #8 
Aug 2019
2·3 Posts 
Everyone has to start somewhere.
Never said there weren't better, faster methods already developed. But clearly everything has a limit. 
20221026, 01:01  #9 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
111001100010_{2} Posts 
I have collected online integer factorizers:
1. https://www.numberempire.com/numberfactorizer.php 2. https://www.alpertron.com.ar/ECM.HTM 3. http://www.javascripter.net/math/cal...calculator.htm 4. https://betaprojects.com/calculators/prime_factors.html 5. https://www.emathhelp.net/calculator...oncalculator/ 6. http://www.numbertheory.org/php/factor.html 7. https://primefan.tripod.com/Factorer.html 8. http://www.se16.info/js/factor.htm 9. http://math.fau.edu/Richman/mla/factorf.htm all of them can factor all numbers with <= 25 bits, most of them can factor all numbers with <= 64 bits also you can use the online MAGMA calculator: http://magma.maths.usyd.edu.au/calc/ Last fiddled with by sweety439 on 20221026 at 01:02 
20221028, 10:30  #10 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3·23·149 Posts 
The easiest/most convenient way is to store 30 numbers in a byte. So, you only need 2^25/30, about 1.1MB. To check if a number >5 is prime, you do a modular division x=q*30+r, and if r is 1, 7, 11, 13, 17, 19, 23 or 29, look at the respective bit in the byte q. (edit: zero indexed, hihi, to shoo the nitpickers )
Last fiddled with by LaurV on 20221028 at 10:35 
20221028, 10:46  #11  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
2·7·263 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring 3^(k*2^n) +/ 1 numbers  lukerichards  Factoring  7  20190410 14:37 
Factoring all of the numbers below 2^100001.  WGJC3107  Factoring  7  20180703 19:36 
Factoring Big Numbers In c#  ShridharRasal  Factoring  10  20080320 17:17 
Factoring Smaller Numbers  marc  Factoring  6  20041009 14:17 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 