mersenneforum.org 18-digit factorization challenge
 Register FAQ Search Today's Posts Mark Forums Read

2020-09-07, 15:15   #12
Alberico Lepore

May 2017
ITALY

7338 Posts

Quote:
 Originally Posted by CRGreathouse In another thread, Alberico Lepore posted: I generated a random "hard" 59-bit semiprime for you: 390644893234047643 with the code Code: rsp(59,2) It (of course) has 18 digits and is of the form pq where p < q < 2p. Would you like to demonstrate how to factor this number step-by-step? (Please don't factor it first by other methods.) As a sidenote, on my old machine, this takes 2.5 ms to factor in gp (using SQUFOF) and about 3 seconds to factor it by trial division. Factorizations of this size can be done by hand; see here for an account of Václav Šimerka's factorization of the 17-digit repunit 11111111111111111 using a precursor of SQUFOF.
N=390644893234047643

I will factor this number without mathematical optimization to understand the procedure

Suppose we don't know that N=(6*i+5)*(6*j+5)

then we will multiply by 25

so we will have

N1=390644893234047643

N2=9766122330851191075

we have to do the same things with N1 and N2 but to speed up we will proceed with N2

we have to bring (b-2*a-1) mod 3 = 0

A=((4*N-1)/9+5)/8 is integer (unambiguous) -> (b-2*a-1) mod 3 = 0

B=((N-1)/9)/2 is integer (ambiguous) -> (b-2*a) mod 3 = 0

C=((7*N-1)/9+4)/14 is integer (ambiguous) -> (b-2*a-2) mod 3 = 0

therefore

9766122330851191075=N2 ,A=((4*N2-1)/9+5)/8 ,((N2-1)/9)/2=B, C=((7*N2-1)/9+4)/14

C is integer

we need to multiply N2 by 7 ^ 2 until we find A integer

if it was B integer we had to multiply by 7

so we will call M1=N2*7^2=478539994211708362675

now to make sure our number is in the form (18*n+1)*(18*m+7) or (18*n+7)*(18*m+1)

we must multiply by
19
7*19
7^2*19

quindi avremo
M1=478539994211708362675
M2=9092259890022458890825
M3=63645819230157212235775
M4=445520734611100485650425

M1=478539994211708362675 ,A=((4*M1-1)/9+5)/8=26585555233983797927 is integer
M2=9092259890022458890825 ,A=((4*M2-1)/9+5)/8=505125549445692160602
M3=63645819230157212235775 ,A=((4*M3-1)/9+5)/8 not integer
M4=445520734611100485650425 ,A=((4*M4-1)/9+5)/8 not integer

we have to do the same things with M1, M2 but to speed up we will proceed with M1

now we should apply
solve (c*18-1)+(7*c+A-1)=(H*w+C)*(6*a+1) , (c*18-1)-(7*c+A-1)=(-K*y-B)*(6*a+1) , c=5*(a+2)/3-3

with C in [0,H-1] e B in [0,K-1]

I'll use random prime numbers without optimizing H=107 and K=173

therefore

solve (c*18-1)+(7*c+A-1)=(107*w+C)*(6*a+1) , (c*18-1)-(7*c+A-1)=(-173*y-B)*(6*a+1) , c=5*(a+2)/3-3

for C = 7 and B = 108 we will have 108 * 108 cycles or 7 * 173 cycles or 108 * 107 or if we implement all three ways 3 * 7 * 173

solve (c*18-1)+(7*c+A-1)=(107*w+7)*(6*a+1) , (c*18-1)-(7*c+A-1)=(-173*y-108)*(6*a+1) , c=5*(a+2)/3-3

solving the diophantine 107*w+7-173*y-108=10

w=(173*t-41) ed y=(107*t-26)

we go to replace and we will have

solve (c*18-1)+(7*c+A-1)=(107*(173*t-41)+7)*(6*a+1) , (c*18-1)-(7*c+A-1)=(-173*(107*t-26)-108)*(6*a+1) , c=5*(a+2)/3-3

therefore

solve (c*18-1)+(7*c+A-1)=(18511*t-4380)*(6*a+1) , (c*18-1)-(7*c+A-1)=(-18511+4390)*(6*a+1) , c=5*(a+2)/3-3

so let's go to solve

solve (c*18-1)+(7*c+26585555233983797927-1)=(18511*t-18511*T-4380)*(6*a+1) , c=5*(a+2)/3-3 ,c,t

t=[(333198*T+78965)*a+55533*T+79756665701951406940 ]/[55533*(6*a+1)]

now we know that

N=p*q con q/p<2 ed abbiamo moltiplicato N per 5^2*7^2

so we will have or

(5*p)*(5*7*7*q)
or
(5*7*p)*(5*7*q)
or
(5*7*7*p)*(5*q)

so we have to evaluate all three cases, but to speed up we will see only the first by looking for n=(a-1)/3

(5*p)*(5*7*7*2*p)-M1=0->

sqrt[M1/2450]=min_p=441952991

5*sqrt(N)=max_p=3125079571

p=18*n+7

min_n=24552943

max_n=173615531

we know that

[6*(55533*T+79756665701951406940)/(-(333198*T+78965))+1]*(-(333198*T+78965))=M1=478539994211708362675

[[6*(55533*T+79756665701951406940)/(-(333198*T+78965))+1]-7]/18=n

then we calculate the min_T and the max_T

[[6*(55533*T+79756665701951406940)/(-(333198*T+78965))+1]-7]/18=min_n=24552943
max_T=-3249674

[[6*(55533*T+79756665701951406940)/(-(333198*T+78965))+1]-7]/18=max_n=173615531
min_T=-459574

in fact T=-567750

so in total there will be cycles

2 N and M

2 M1 and M2

3*7*173 to locate C and B

3 to calculate min_T and max_T

2*2*3*7*173*3*(567750-459574)=4716040896 cicles

about like the trial division but I factored this number without mathematical optimization to understand the procedure

and without using these formulas

4)
a=3*n+1 ; m =3*k , A=54*k*n+21*k+n+1

5)
a=3*n+1 ; m =3*k+1 , A=54*k*n+21*k+19*n+8

6)
a=3*n+1 ; m =3*k+2 , A=54*k*n+21*k+37*n+15

2020-09-07, 16:58   #13
mathwiz

Mar 2019

149 Posts

Quote:
 Originally Posted by Alberico Lepore about like the trial division but I factored this number without mathematical optimization to understand the procedure
And the factors are...?

2020-09-07, 17:31   #14
Alberico Lepore

May 2017
ITALY

47510 Posts

Quote:
 Originally Posted by mathwiz And the factors are...?
N=505928201*772135043=390644893234047643

2020-09-08, 13:50   #15
Alberico Lepore

May 2017
ITALY

52·19 Posts

Quote:
 Originally Posted by CRGreathouse In another thread, Alberico Lepore posted: I generated a random "hard" 59-bit semiprime for you: 390644893234047643 with the code Code: rsp(59,2) It (of course) has 18 digits and is of the form pq where p < q < 2p. Would you like to demonstrate how to factor this number step-by-step? (Please don't factor it first by other methods.) As a sidenote, on my old machine, this takes 2.5 ms to factor in gp (using SQUFOF) and about 3 seconds to factor it by trial division. Factorizations of this size can be done by hand; see here for an account of Václav Šimerka's factorization of the 17-digit repunit 11111111111111111 using a precursor of SQUFOF.
Quote:
 Originally Posted by mathwiz And the factors are...?

I still don't formalize it

I post the example proposed by CRGreathouse N=390644893234047643

M1=478539994211708362675 -> A=26585555233983797927

I found a solution in 75 log

n_min=0

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 ,n=0 ,K=0 -> H_max=3797936461997685417

n_max=(sqrt(M1)-7)/18=1215308722

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 ,n=1215308722 ,K=0 -> H_min=1215308721

We start from 2 and logarithmically we find the range of H where for H-2 solving the diophantine as a function of a variable m
n = Y-m
Y scale of 1
n = Y-1-m
In our case, arrived at 75 we find the range for which H-75 makes the Y scale by 1 which is [10509615638, 10509615863]

solving the Diophantine we will have n = Y-m, K = Z * m + X

if X / (18 * Y + 7)> 75-1 = 74 we have to make H rise

if X / (18 * Y + 7) <75-1 = 74 we have to bring down H

if X / (18 * Y + 7) = 75-1 = 74 GCD (X, N) = p

I leave you some calculations for 75

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-224

n=140535613-m ,K=189173081503*m+188293422114 -> 188293422114/(18*140535613+7)=74,43

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-150

n=140535613-m ,K=189173082835*m+1099985080

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-149

n=140535612-m ,K=189173082853*m+187743426892 -> 187743426892/(18*140535612+7)=74,217

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-76

n=140535612-m ,K=189173084167*m+3079632213

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-75

n=140535612-m ,K=189173084185*m+549991190

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-74

n=140535611-m ,K=189173084203*m+187193434370 -> 187193434370 /(18*140535611+7)=74

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-2

n=140535611-m ,K=189173085499*m+5059282010

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862-1

n=140535611-m ,K=189173085517*m+2529641005

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862

n=140535611-m ,K=189173085535*m -> 0/(18*140535611+7)=0

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862+1

n=140535610-m ,K=189173085553*m+186643444548 ->186643444548/(18*140535611+7)=73,78

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862+2

n=140535610-m ,K=189173085571*m+184113803561

2/3*[26585555233983797927*3-2-(6*(3*n+1)+1)-3*H*(6*(3*n+1)+1)]-2*K=((6*(3*n+1)+1)*13-1)/9 , H=10509615862+3

n=140535610-m ,K=189173085589*m+181584162574

 2020-09-08, 14:05 #16 Alberico Lepore     May 2017 ITALY 7338 Posts I don't know if 75 is always valid for 75 - 1 = 74 bad that goes is 75 * 75 * log I just found these things and immediately shared them with you

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 1 2020-05-27 12:20 sweety439 Computer Science & Computational Number Theory 0 2020-02-11 03:12 MattcAnderson Puzzles 4 2016-02-29 08:57 devarajkandadai Miscellaneous Math 0 2012-05-31 05:17 AntonVrba Factoring 7 2005-12-06 22:02

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

Sat Apr 17 10:46:33 UTC 2021 up 9 days, 5:27, 0 users, load averages: 2.70, 2.37, 2.30