mersenneforum.org Factoring 1 - 25 bit numbers
 Register FAQ Search Today's Posts Mark Forums Read

2022-10-23, 14:30   #1
Jombo G

Aug 2019

2×3 Posts
Factoring 1 - 25 bit numbers

Hello there. Attached is PARI-GP code without any modular tricks, just a very basic bare bones factoring method.
It will probably factor up to 32-bit semi-prime 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 25-bits could probably be extended to at least 50-75 using modular arithmetic, but it takes time to learn.

Have a nice day.
Attached Files
 Basic Method sans modular arithmetic.txt (321 Bytes, 59 views)

 2022-10-23, 17:00 #2 xilman Bamboozled!     "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 101101100101002 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.
 2022-10-23, 19:48 #3 ThiloHarich     Nov 2005 22×33 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^(25-1) 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 2022-10-23 at 20:27
2022-10-24, 02:01   #4
axn

Jun 2003

10101001111102 Posts

Quote:
 Originally Posted by ThiloHarich A lookup table indicating if a odd number below 2^25 is composite would be around 2^(25-1) bit = 2^(25 - 1 -3) byte ~ 2 GB.
2^21 bits = 2MB

A two byte lookup for the smallest factor = 16x that = 32 MB

 2022-10-24, 15:36 #5 chris2be8     Sep 2009 22·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.)
 2022-10-24, 18:09 #6 Jombo G   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 (even-ish - meaning rougly same lengths of factors in terms of digits) semi-primes, 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 semi-primes of various sizes: https://asecuritysite.com/encryption/random3?val=32 Last fiddled with by Jombo G on 2022-10-24 at 18:10
2022-10-24, 19:06   #7
kruoli

"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:
 Time elapsed: 0d 0h 0m 0.0s Modular multiplications: ECM: 45076 Probable prime checking: 183 Sum of squares: 250 Timings: Probable prime test of 2 numbers: 0d 0h 0m 0.0s Factoring 1 number using ECM: 0d 0h 0m 0.0s

 2022-10-24, 19:20 #8 Jombo G   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.
 2022-10-26, 01:01 #9 sweety439   "99(4^34019)99 palind" Nov 2016 (P^81993)SZ base 36 1110011000102 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...on-calculator/ 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/factor-f.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 2022-10-26 at 01:02
2022-10-28, 10:30   #10
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

3·23·149 Posts

Quote:
 Originally Posted by ThiloHarich How will a 32 MB entry table look like?
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 2022-10-28 at 10:35

2022-10-28, 10:46   #11
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2·7·263 Posts

Quote:
 Originally Posted by LaurV 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 )
There are 256GB (i.e. 2^38 bytes) systems thus storing the first 2^38 primes in a computer may be possible?

 Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Factoring 7 2019-04-10 14:37 WGJC3107 Factoring 7 2018-07-03 19:36 ShridharRasal Factoring 10 2008-03-20 17:17 marc Factoring 6 2004-10-09 14:17 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 10:02.

Thu Feb 9 10:02:33 UTC 2023 up 175 days, 7:31, 1 user, load averages: 1.03, 0.93, 0.87