mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-09-05, 05:13   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

17×349 Posts
Default 18-digit factorization challenge

In another thread, Alberico Lepore posted:

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

3×5×31 Posts
Default

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
Alberico Lepore is offline   Reply With Quote
Old 2020-09-05, 09:21   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×7×163 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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."
Batalov is offline   Reply With Quote
Old 2020-09-05, 09:28   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·5·31 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 is offline   Reply With Quote
Old 2020-09-05, 09:41   #5
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 Alberico Lepore View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2020-09-05, 16:52   #6
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

521 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
Dylan14 is offline   Reply With Quote
Old 2020-09-05, 17:13   #7
mathwiz
 
Mar 2019

10210 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
mathwiz is offline   Reply With Quote
Old 2020-09-05, 17:41   #8
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1110100012 Posts
Cry

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.
Alberico Lepore is offline   Reply With Quote
Old 2020-09-05, 17:57   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,409 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
VBCurtis is offline   Reply With Quote
Old 2020-09-06, 00:19   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

593310 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-09-07, 12:19   #11
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

3·5·31 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
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 20:11.

Fri Oct 30 20:11:52 UTC 2020 up 50 days, 17:22, 1 user, load averages: 2.29, 2.16, 2.04

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.