Factoring 1 - 25 bit numbers

[Jombo G]

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.



Thanks for reading.



Have a nice day.

[xilman]

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.

[ThiloHarich]

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).

[axn]

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

[chris2be8]

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.)

[Jombo G]

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

[kruoli]

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":

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

[Jombo G]

Everyone has to start somewhere.

Never said there weren't better, faster methods already developed. But clearly everything has a limit.

[sweety439]

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/

[LaurV]

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 )

[sweety439]

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?