18-digit factorization challenge

[CRGreathouse]

In another thread, Alberico Lepore posted:

Originally Posted by Alberico Lepore

I've factored 18 digits number, but I need help optimizing the algorithm.

https://mersenneforum.org/showthread...028#post556028

I generated a random "hard" 59-bit semiprime for you:
390644893234047643
with the 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.

[Alberico Lepore]

N=390644893234047643 , (N-1)/6=F

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

F is integer

A,B,C not integer

-> N=(6*a+5)*(6*b+5)

to be optimized this method needs two factors 18 * t + 1 and 18 * s + 7

[Batalov]

Originally Posted by Alberico Lepore

to be optimized this method needs ...

What method? "Where is the method, Lebowski? Where are the factors? We need those factors! "

"Where's the money, Lebowski?" -- "It's down there somewhere, let me take another look."

[Alberico Lepore]

Originally Posted by Batalov

What method? "Where is the method, Lebowski? Where are the factors? We need those factors! "

"Where's the money, Lebowski?" -- "It's down there somewhere, let me take another look."

“Mind if I do a J?”

[Alberico Lepore]

Originally Posted by CRGreathouse

In another thread, Alberico Lepore posted:



I generated a random "hard" 59-bit semiprime for you:
390644893234047643
with the 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.

Originally Posted by Alberico Lepore

N=390644893234047643 , (N-1)/6=F

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

F is integer

A,B,C not integer

-> N=(6*a+5)*(6*b+5)

to be optimized this method needs two factors 18 * t + 1 and 18 * s + 7

if you give it to me correct I will use 107 and 173.
but don't cheat

[Dylan14]

Originally Posted by Alberico Lepore

N=390644893234047643 , (N-1)/6=F

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

F is integer

A,B,C not integer

-> N=(6*a+5)*(6*b+5)

to be optimized this method needs two factors 18 * t + 1 and 18 * s + 7

Running your choice of equations, I get the following:
F = 65107482205674607
A = 781289786468095309/36
B = 65107482205674607/3
C = 65107482205674608/3

so you are correct that F is an integer, and A, B and C are not. Then you claim
N = (6*a+5)*(6*b+5)

presuming a and b in this equation are the same as A and B above, we have

390644893234047643 = 101735621739893665192780582115190241/6

which is false.
Also, what is t and what is s? You have not defined what these are.

[mathwiz]

Originally Posted by Alberico Lepore

if you give it to me correct I will use 107 and 173.
but don't cheat

But I want to cheat. It's so tempting... Otherwise this number may never be factored.

[Alberico Lepore]

Until Tuesday I will be on standby.
There is a serious possibility that I will not be able to continue my studies on factorization.
I will read the posts but I will be unable to reply.
We hope well.

[VBCurtis]

Originally Posted by Alberico Lepore

There is a serious possibility that I will not be able to continue my studies on factorization.
.

There is no evidence you've ever started any studies on factorization. If you had, you wouldn't waste everyone's time with these useless equations.

[CRGreathouse]

Originally Posted by Alberico Lepore

Until Tuesday I will be on standby.
There is a serious possibility that I will not be able to continue my studies on factorization.
I will read the posts but I will be unable to reply.
We hope well.

I hope you and your family are well. Take as long as you need.

[Alberico Lepore]

Originally Posted by CRGreathouse

I hope you and your family are well. Take as long as you need.

thanks for your interest.
everything went well, I will be able to continue my amateur studies on factorzation.
I'll factor in your number, just give me a few days to recover.