mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2020-09-07, 15:15   #12
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

46510 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2020-09-07, 16:58   #13
mathwiz
 
Mar 2019

22·52 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
about like the trial division but I factored this number without mathematical optimization to understand the procedure
And the factors are...?
mathwiz is offline   Reply With Quote
Old 2020-09-07, 17:31   #14
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

46510 Posts
Default

Quote:
Originally Posted by mathwiz View Post
And the factors are...?
N=505928201*772135043=390644893234047643
Alberico Lepore is offline   Reply With Quote
Old 2020-09-08, 13:50   #15
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·5·31 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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 View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2020-09-08, 14:05   #16
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3×5×31 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Phantom factorization - subcubic factorization of integers? Alberico Lepore Alberico Lepore 1 2020-05-27 12:20
Find Kaprekar's constants and cycles of the Kaprekar mapping of 9-digit to 12-digit numbe in base 12 sweety439 Computer Science & Computational Number Theory 0 2020-02-11 03:12
5 digit factorization MattcAnderson Puzzles 4 2016-02-29 08:57
A Challenge on the net devarajkandadai Miscellaneous Math 0 2012-05-31 05:17
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02

All times are UTC. The time now is 04:11.

Sat Oct 24 04:11:57 UTC 2020 up 44 days, 1:22, 1 user, load averages: 1.61, 1.56, 1.45

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