mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > storflyt32

Reply
 
Thread Tools
Old 2013-11-18, 17:08   #1
storflyt32
 
Feb 2013

2×229 Posts
Default Unwilling number.

A number I came across a little while ago.

125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851

This number is not willing to factorize.

Can anyone offer some advice please?

Thanks!
storflyt32 is offline   Reply With Quote
Old 2013-11-18, 17:23   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

10AD16 Posts
Default

You can use YAFU to factorize that number (a c96, which means a 96-digit composite) in a fairly short amount of time (seconds, minutes, or hours for a number of this size, depending on what it takes to crack it). It will use ECM, QS, NFS, etc. as needed to find its factors in the best time it can. Use this command:

Code:
factor(125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851)
(assuming the number isn't of a particularly special form and hasn't been checked for factors to a significant depth, that's a good way to have YAFU do some factorization efforts before going to the long QS/NFS factorization methods)

Last fiddled with by Mini-Geek on 2013-11-18 at 17:30
Mini-Geek is offline   Reply With Quote
Old 2013-11-18, 18:05   #3
Ralf Recker
 
Ralf Recker's Avatar
 
Oct 2010

191 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
(seconds, minutes, or hours for a number of this size, depending on what it takes to crack it)
10 minutes 6 seconds with NFS. Probably faster with ECM depending on your luck:

Code:
GMP-ECM 7.0-dev [configured with GMP 5.1.3, --enable-asm-redc, --enable-gpu, --enable-assert, --enable-openmp] [ECM]
Using B1=1000000, B2=1045563762, polynomial Dickson(6), 8 threads
Done 297/2400; avg s/curve: stg1 2.115s, stg2 1.427s; runtime: 137s

Run 297 out of 2400:
Using B1=1000000, B2=1045563762, polynomial Dickson(6), sigma=1:3545553215
Step 1 took 2116ms
Step 2 took 1436ms
********** Factor found in step 2: 1576422053186621557751857821413401
Found probable prime factor of 34 digits: 1576422053186621557751857821413401
Probable prime cofactor 79400694418664331852968752783562533762348560846718294611714451 has 62 digits
Note to myself: 2400 curves for 3e6...

Last fiddled with by Ralf Recker on 2013-11-18 at 18:07
Ralf Recker is offline   Reply With Quote
Old 2013-11-18, 18:07   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

3.28 seconds for me.

Guess I got lucky .
bsquared is offline   Reply With Quote
Old 2013-11-18, 18:25   #5
Ralf Recker
 
Ralf Recker's Avatar
 
Oct 2010

19110 Posts
Default

Quote:
Originally Posted by bsquared View Post
3.28 seconds for me.

Guess I got lucky .
FactorDB?
Ralf Recker is offline   Reply With Quote
Old 2013-11-18, 18:28   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by Ralf Recker View Post
FactorDB?
Code:
% ./yafu "factor(125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851)" -v -threads 16


11/18/13 12:06:23 v1.34.5 @ gree.mayo.edu, System/Build Info:
Using GMP-ECM 6.4.4, Powered by GMP 5.1.1
detected        Intel(R) Xeon(R) CPU E5-4650 0 @ 2.70GHz
detected L1 = 32768 bytes, L2 = 20971520 bytes, CL = 64 bytes
measured cpu frequency ~= 2699.961480
using 20 random witnesses for Rabin-Miller PRP checks

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983


>> fac: factoring 125169005719914348816520676003006990595104088750459775327657394996598953675214064913848636757851
fac: using pretesting plan: normal
fac: using tune info for qs/gnfs crossover
div: primes less than 10000
rho: x^2 + 3, starting 1000 iterations on C96
rho: x^2 + 2, starting 1000 iterations on C96
rho: x^2 + 1, starting 1000 iterations on C96
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
pm1: starting B1 = 150K, B2 = gmp-ecm default on C96
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
fac: sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t22.97
ecm: 30/30 curves on C96, B1=2K, B2=gmp-ecm default
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
fac: t15: 1.00
fac: t20: 0.04
fac: sum of completed work is t15.18
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t22.97
ecm: 74/74 curves on C96, B1=11K, B2=gmp-ecm default
fac: ecm effort reduced from 29.54 to 22.97: input has snfs form
fac: setting target pretesting digits to 22.97
fac: t15: 7.17
fac: t20: 1.04
fac: t25: 0.05
fac: sum of completed work is t20.24
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 117 more curves at B1=50000 needed to get to t22.97
ecm: 16/128 curves on C96, B1=50K, B2=gmp-ecm default, ETA: 2 sec
ecm: found prp34 factor = 1576422053186621557751857821413401

fac: ecm effort reduced from 19.08 to 14.84: input has snfs form
fac: setting target pretesting digits to 14.84
fac: t15: 11.74
fac: t20: 2.56
fac: t25: 0.20
fac: t30: 0.01
fac: sum of completed work is t20.99
pretesting / qs ratio was 86.03
Total factoring time = 3.2817 seconds


***factors found***

P34 = 1576422053186621557751857821413401
P62 = 79400694418664331852968752783562533762348560846718294611714451

ans = 1
But apparently the input has a SNFS form, so even if the ecm factor was missed it would have only taken a few minutes, as you said.
bsquared is offline   Reply With Quote
Old 2013-11-18, 18:31   #7
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

110111110002 Posts
Default

Code:
Lanczos elapsed time = 48.2060 seconds.
Sqrt elapsed time = 0.7590 seconds.
SIQS elapsed time = 1325.4398 seconds.
pretesting / qs ratio was 0.30
Total factoring time = 1727.5118 seconds


***factors found***

P34 = 1576422053186621557751857821413401
P62 = 79400694418664331852968752783562533762348560846718294611714451
Apparently I was very unlucky...
wombatman is offline   Reply With Quote
Old 2013-11-18, 19:01   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3·1,423 Posts
Default

Quote:
Originally Posted by bsquared View Post
Code:
ecm: 16/128 curves on C96, B1=50K, B2=gmp-ecm default, ETA: 2 sec
ecm: found prp34 factor = 1576422053186621557751857821413401
That's an incredibly lucky find! Do you happen to have the sigma for that?

I found the p34 factor as well, with B1=250000 bounds, sigma 1938467591. That group order factors as [ <2, 3>, <3, 1>, <6151, 1>, <65353, 1>, <91961, 1>, <92593, 1>, <153719, 1>, <124836221, 1> ]

I get Ralf Recker's sigma (assuming it's 3545553215), as [ <2, 3>, <3, 2>, <4909, 1>, <4460124412039738652099414071, 1> ] so either the Dickson polynomial threw in the large factor, or I need to do something to account for the "1:" before it.

Last fiddled with by Mini-Geek on 2013-11-18 at 19:01
Mini-Geek is offline   Reply With Quote
Old 2013-11-18, 19:08   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
That's an incredibly lucky find! Do you happen to have the sigma for that?

I found the p34 factor as well, with B1=250000 bounds, sigma 1938467591. That group order factors as [ <2, 3>, <3, 1>, <6151, 1>, <65353, 1>, <91961, 1>, <92593, 1>, <153719, 1>, <124836221, 1> ]

I get Ralf Recker's sigma (assuming it's 3545553215), as [ <2, 3>, <3, 2>, <4909, 1>, <4460124412039738652099414071, 1> ] so either the Dickson polynomial threw in the large factor, or I need to do something to account for the "1:" before it.
Code:
11/18/13 12:06:27 v1.34.5 @ xxx.yyy.zzz, prp34 = 1576422053186621557751857821413401 (curve 2 stg2 B1=50000 sigma=2945162712 thread=13)
bsquared is offline   Reply With Quote
Old 2013-11-18, 19:38   #10
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

3×1,423 Posts
Default

That group order is indeed very smooth:
[ <2, 4>, <3, 2>, <7, 1>, <47, 1>, <269, 1>, <6899, 1>, <8243, 1>, <15607, 1>, <17497, 1>, <48487, 1>, <164279, 1> ]
GMP-ECM reports that the expected number of curves at those bounds to find a factor of 35 digits is 69076 (34 digits will be close). We collectively have surely run this early ECM way too much, maybe 1000 or 2000 curves? Even so, I estimate a 1-3% chance of finding it at these bounds.
Given the ECM depth that YAFU targets, the most likely course of action for this number should be to QS or GNFS it. Either due to sampling bias (we are more likely to post here if we find it than if we fail, or cancel during QS/NFS) or luck, we seem to be finding this factor far more often than that!

It's worth noting that the number that this thread is all about is a cofactor of 2^725+1, which has already been factored.

Last fiddled with by Mini-Geek on 2013-11-18 at 19:43
Mini-Geek is offline   Reply With Quote
Old 2013-11-19, 23:57   #11
storflyt32
 
Feb 2013

2·229 Posts
Default

2^1968721+1 has a factor 3 ...
storflyt32 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding multiples of a real number that are close to a whole number mickfrancis Math 16 2017-03-01 07:17
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46
Number 59649589127497217 is a factor of Fermat number F7 literka Miscellaneous Math 73 2013-11-17 10:33
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28

All times are UTC. The time now is 08:09.


Thu Oct 28 08:09:12 UTC 2021 up 97 days, 2:38, 0 users, load averages: 2.24, 2.04, 1.98

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