mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-10-23, 14:30   #1
Jombo G
 
Aug 2019

2×3 Posts
Post 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.



Thanks for reading.



Have a nice day.
Attached Files
File Type: txt Basic Method sans modular arithmetic.txt (321 Bytes, 59 views)
Jombo G is offline   Reply With Quote
Old 2022-10-23, 17:00   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101101100101002 Posts
Default

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.
xilman is offline   Reply With Quote
Old 2022-10-23, 19:48   #3
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

22×33 Posts
Default

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
ThiloHarich is offline   Reply With Quote
Old 2022-10-24, 02:01   #4
axn
 
axn's Avatar
 
Jun 2003

10101001111102 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
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
axn is offline   Reply With Quote
Old 2022-10-24, 15:36   #5
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·607 Posts
Default

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.)
chris2be8 is offline   Reply With Quote
Old 2022-10-24, 18:09   #6
Jombo G
 
Aug 2019

2×3 Posts
Post 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
Jombo G is offline   Reply With Quote
Old 2022-10-24, 19:06   #7
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

17×79 Posts
Default

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
kruoli is offline   Reply With Quote
Old 2022-10-24, 19:20   #8
Jombo G
 
Aug 2019

2·3 Posts
Smile

Everyone has to start somewhere.

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



Jombo G is offline   Reply With Quote
Old 2022-10-26, 01:01   #9
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

1110011000102 Posts
Default

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
sweety439 is offline   Reply With Quote
Old 2022-10-28, 10:30   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

3·23·149 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
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
LaurV is offline   Reply With Quote
Old 2022-10-28, 10:46   #11
sweety439
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

2·7·263 Posts
Default

Quote:
Originally Posted by LaurV View Post
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?
sweety439 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring 3^(k*2^n) +/- 1 numbers lukerichards Factoring 7 2019-04-10 14:37
Factoring all of the numbers below 2^10000-1. WGJC3107 Factoring 7 2018-07-03 19:36
Factoring Big Numbers In c# ShridharRasal Factoring 10 2008-03-20 17:17
Factoring Smaller Numbers marc Factoring 6 2004-10-09 14:17
Factoring Fermat Numbers 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”