Software to factor arbitrary ~410-bit number - Page 2

bsquared · 2019-05-16, 13:39

Quote:

Originally Posted by VBCurtis

NFS factoring difficulty doubles about every 5 digits, so 48 bits smaller is about 8x faster to factor than the original 410-bit number.
Here are your factors:

Code:

80372772078870023311028629526527251806209541
79001680667399413021755551127728881024073264821649477463074552981

50 minutes wall-clock time on 8 hyperthreads.

For fun... 36 minutes by SIQS:

Code:

starting SIQS on c109: 6349584074128565251579621474009238287623563015787101780061041692025765962232486337920863526534965038592191721

==== sieve params ====
n = 109 digits, 362 bits
factor base: 207584 primes (max prime = 6041731)
single large prime cutoff: 906259650 (150 * pmax)
double large prime range from 46 to 54 bits
double large prime range from 36502513476361 to 13275618366497020
allocating 12 large prime slices of factor base
buckets hold 2048 elements
large prime hashtables have 2359296 bytes
using AVX512 enabled 32k sieve core
sieve interval: 12 blocks of size 32768
polynomial A has ~ 14 factors
using multiplier of 1
using SPV correction of 20 bits, starting at offset 29
trial factoring cutoff at 109 bits

==== sieving in progress (256 threads):  207648 relations needed ====
====             Press ctrl-c to abort and save state            ====
213768 rels found: 51473 full + 162295 from 3078485 partial, (1537.69 rels/sec)

sieving required 22440891 total polynomials (5773 'A' polynomials)
trial division touched 816476743 sieve locations out of 17648234790912
squfof: 0 failures, 2482767 attempts, 457120483 outside range, 12555665 prp, 2321648 useful
total reports = 816476743, total surviving reports = 472967225
total blocks sieved = 538587336,avg surviving reports per block = 0.88
QS elapsed time = 2035.4923 seconds.
...
lanczos halted after 3118 iterations (dim = 197110)
recovered 14 nontrivial dependencies
Lanczos elapsed time = 93.3500 seconds.
Sqrt elapsed time = 0.7600 seconds.
SIQS elapsed time = 2131.4362 seconds.


***factors found***

P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981

axn · 2019-05-16, 13:56

Quote:

Originally Posted by bsquared

For fun... 36 minutes by SIQS:

256 threads?

What processor is that?

bsquared · 2019-05-16, 14:27

Quote:

Originally Posted by axn

256 threads?

What processor is that?

Quote:

Originally Posted by yafu v1.35-beta

detected Intel(R) Xeon Phi(TM) CPU 7210 @ 1.30GHz
detected L1 = 32768 bytes, L2 = 1048576 bytes, CL = 64 bytes
measured cpu frequency ~= 1297.000770

64 cores, 4 hyperthreads per core; it acts like a sieve-friendly GPU.

James Heinrich · 2019-05-16, 14:30

Quote:

Originally Posted by James Heinrich

yafu... why didn't I yafu... I have it installed already, just forgot about it.

So I let it run for an hour or two overnight and it did exactly what I wanted:

Code:

yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12

P1 = 2
P1 = 2
P2 = 17
P2 = 43
P4 = 1907
P9 = 148922387
P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981

albeit extremely verbosely with tens (hundreds?) of thousands of lines of stuff like:

Code:

2484 124809929372509 224852862953705734163711291
2736 81689936843131 219486238756129466725063989
2736 148682315369983 219486238756588041585847851
2484 162497197129847 224852862957929937234699210
2484 258181694630701 224852862955171329218701786
2484 79893963420767 224852862959184885179883596
2736 52015090684045 219486238755244569165277559
2484 95260187304253 224852862957853214745664415
2484 123822558294469 224852862954159224783743291
2736 77036731878323 219486238752425401447998675
2484 104582954047259 224852862955390973830660807
2736 99968994776407 219486238757645654923105819
2736 236049971433649 219486238752721810750461124
2736 96202602994523 219486238754915888222368567
2736 111855459347017 219486238756502505324264408
2736 236049971433649 219486238752721810750461124
2736 174430633987859 219486238750088021464795804
2484 80433616080781 224852862959206056424178599
2484 112743893490227 224852862959183716661681013
2484 95887700959069 224852862955704924321522300
2736 203203689199651 219486238764784090149645668
2484 104197709439407 224852862957113690143384847
2736 103246625437715 219486238759337210812421743
2484 216599904445571 224852862956048355481589736
2484 85357935594391 224852862956095450796170855
2736 68407037230045 219486238752340869238887827
2736 162996849442985 219486238757483785913262416
2484 85967592141049 224852862956184628184011883
2736 411261153225155 219486238758742013983637186
2736 231679070567137 219486238755140736617124507
2736 2760880173455 219486238755276485706764776

I couldn't find a "quiet" switch to make it less verbose.

xilman · 2019-05-16, 14:56

Quote:

Originally Posted by James Heinrich

So I let it run for an hour or two overnight and it did exactly what I wanted:

Code:

yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12

P1 = 2
P1 = 2
P2 = 17
P2 = 43
P4 = 1907
P9 = 148922387
P44 = 80372772078870023311028629526527251806209541
P65 = 79001680667399413021755551127728881024073264821649477463074552981

albeit extremely verbosely with tens (hundreds?) of thousands of lines of stuff like:

Code:

2484 124809929372509 224852862953705734163711291
2736 81689936843131 219486238756129466725063989
2736 148682315369983 219486238756588041585847851
2484 162497197129847 224852862957929937234699210
2484 258181694630701 224852862955171329218701786
2484 79893963420767 224852862959184885179883596
2736 52015090684045 219486238755244569165277559
2484 95260187304253 224852862957853214745664415
2484 123822558294469 224852862954159224783743291
2736 77036731878323 219486238752425401447998675
2484 104582954047259 224852862955390973830660807
2736 99968994776407 219486238757645654923105819
2736 236049971433649 219486238752721810750461124
2736 96202602994523 219486238754915888222368567
2736 111855459347017 219486238756502505324264408
2736 236049971433649 219486238752721810750461124
2736 174430633987859 219486238750088021464795804
2484 80433616080781 224852862959206056424178599
2484 112743893490227 224852862959183716661681013
2484 95887700959069 224852862955704924321522300
2736 203203689199651 219486238764784090149645668
2484 104197709439407 224852862957113690143384847
2736 103246625437715 219486238759337210812421743
2484 216599904445571 224852862956048355481589736
2484 85357935594391 224852862956095450796170855
2736 68407037230045 219486238752340869238887827
2736 162996849442985 219486238757483785913262416
2484 85967592141049 224852862956184628184011883
2736 411261153225155 219486238758742013983637186
2736 231679070567137 219486238755140736617124507
2736 2760880173455 219486238755276485706764776

I couldn't find a "quiet" switch to make it less verbose.

Redirect STDIN and STDERR to /dev/null

James Heinrich · 2019-05-16, 15:04

Quote:

Originally Posted by xilman

Redirect STDIN and STDERR to /dev/null

I didn't even know that STDERR was a thing in Windows, but it is, and that helps, thanks.

Code:

yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12 2> nul

retina · 2019-05-16, 15:16

Quote:

Originally Posted by xilman

Redirect STDIN [snip] to /dev/null

STDIN?

Two men are having a conversation, but both are only listening.

kriesel · 2019-05-16, 15:19

Quote:

Originally Posted by James Heinrich

I didn't even know that STDERR was a thing in Windows, but it is, and that helps, thanks.

Code:

yafu-x64 "factor(5272703229220007874811133810104969405477368739513286723394714036551930163895517204360421097050187418157101219550018359697836)" -p -threads 12 2> nul

Hasn't it been a thing on MS operating systems since c compilers on MSDOS?
STDERR redirects differently than STDOUT. If a programmer is not careful, a STDOUT portion of an error message gets redirected and the STDERR portion still goes to the cmd console, unless the user takes rare care.

https://stackoverflow.com/questions/...on-windows-dos

xilman · 2019-05-16, 15:24

Quote:

Originally Posted by retina

STDIN?

Two men are having a conversation, but both are only listening.

UBD

LaurV · 2019-05-17, 04:48

Quote:

Originally Posted by kriesel

Hasn't it been a thing on MS operating systems since c compilers on MSDOS?

It has, but we all have our strengths and weaknesses, and not all people are "old dinosaurs" like us. Some barely remember WinXP or '98, and only heard "DOS" in the "DoS" context (Denial of Service).

Uncwilly · 2019-05-17, 05:15

CP/M wants to play too.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Factor-finding algorithms (and software)	lukerichards	Factoring	87	2019-03-28 13:31
Prime number software.	Zach010	Software	21	2019-01-11 05:51
Number 59649589127497217 is a factor of Fermat number F7	literka	Miscellaneous Math	73	2013-11-17 10:33
software advise? big number with GUI	skan	Programming	14	2013-03-24 00:32
Time to test arbitrary number	JuanTutors	Math	3	2007-05-16 12:13

2019-05-17, 05:15	#22
Uncwilly 6809 > 6502 """"""""""""""""""" Aug 2003 101×103 Posts 2×4,909 Posts	CP/M wants to play too.