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

2020-09-05, 05:13   #1
CRGreathouse

Aug 2006

3×1,993 Posts
18-digit factorization challenge

In another thread, Alberico Lepore posted:

Quote:
 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
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.

 2020-09-05, 09:05 #2 Alberico Lepore     May 2017 ITALY 2×32×29 Posts 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 Last fiddled with by Alberico Lepore on 2020-09-05 at 09:08
2020-09-05, 09:21   #3
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×5×983 Posts

Quote:
 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."

2020-09-05, 09:28   #4
Alberico Lepore

May 2017
ITALY

10000010102 Posts

Quote:
 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?”

2020-09-05, 09:41   #5
Alberico Lepore

May 2017
ITALY

10128 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 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

2020-09-05, 16:52   #6
Dylan14

"Dylan"
Mar 2017

24×37 Posts

Quote:
 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.

2020-09-05, 17:13   #7
mathwiz

Mar 2019

2×131 Posts

Quote:
 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.

 2020-09-05, 17:41 #8 Alberico Lepore     May 2017 ITALY 2×32×29 Posts 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.
2020-09-05, 17:57   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

10100101001002 Posts

Quote:
 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.

2020-09-06, 00:19   #10
CRGreathouse

Aug 2006

3·1,993 Posts

Quote:
 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.

2020-09-07, 12:19   #11
Alberico Lepore

May 2017
ITALY

20A16 Posts

Quote:
 Originally Posted by CRGreathouse I hope you and your family are well. Take as long as you need.
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.

 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 14:03.

Wed May 25 14:03:22 UTC 2022 up 41 days, 12:04, 0 users, load averages: 1.06, 1.14, 1.17