 mersenneforum.org 18-digit factorization challenge
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2020-09-07, 15:15   #12
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.
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

14910 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

52×19 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 52·19 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   Thread Tools Show Printable Version Email this Page 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 12:21.

Sat Apr 17 12:21:50 UTC 2021 up 9 days, 7:02, 0 users, load averages: 2.21, 2.08, 2.02

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.