Lepore Factorization in O(k) Conjecture

Alberico Lepore · 2017-08-30, 10:57

Lepore Factorization in O(k) Conjecture

https://www.academia.edu/34408457/Le...O_k_Conjecture

Do you think about it?

CRGreathouse · 2017-08-30, 16:28

I don't see either a conjecture or an algorithm there. But I have a conjecture of my own: any paper which spends more than half its length exploring the consequences of numbers being of the form 6n ± 1 is unlikely to make an algorithmic or number-theoretic breakthrough.

I know my conjecture seems oddly specific, but I've seen it pretty often. (At least with half replaced with a more reasonable fraction like a tenth.)

Batalov · 2017-08-31, 00:19

Quote:

Originally Posted by Alberico Lepore

https://www.academia.edu/34408457/Le...O_k_Conjecture

Do you think about it?

Quote:

Page Not Found
Sorry. We can't find the page you're looking for.

In addition to Charles' conjecture, here's another one:

Any paper that has the author's name also in the title is not worth reading.
(e.g. J.Kruasandwich, "The Kruasandwich method of turning lead into gold". Stop right there. Don't read it.)

Alberico Lepore · 2017-09-03, 09:26

Look this

https://www.academia.edu/34339494/Fa...t%C3%A0_random

And think this
If we go to look directly, numbers with k <n elements the game is done.

feedback please

thank you

jnml · 2017-09-03, 10:24

Quote:

Originally Posted by Alberico Lepore

Look this

https://www.academia.edu/34339494/Fa...t%C3%A0_random

And think this
If we go to look directly, numbers with k <n elements the game is done.

feedback please

thank you

PSA: Let me advise anyone against downloading the paper for at least two reasons: it has authors name in its title (cf. Batalov's post above) and downloading it requires to "connect" with the author on G+ or FB. Would the intents of the author be fair, there're zero reasons to hide the paper behind any paywall/"connectwall" etc.

And if you do download the paper and you're using a popular unsecure OS, do not open the document without performing proper AV checks.

Alberico Lepore · 2017-09-03, 10:27

Fattorizzazione RSA di Lepore
Complessità random

Definizione
Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5.
Dimostrazione
NR modulo 6 =1 -> 6h+1
NR modulo 6 =2 -> è multiplo di 2
NR modulo 6 =3 -> è multiplo di 3
NR modulo 6 =4 -> è multiplo di 2
NR modulo 6 =5 -> 6h+5
NR modulo 6 =0 -> è multiplo di 2 e di 3

Lemma
Quindi partendo da 1 e facendo +4 e +2 si ha 1 5 7 11 13 17 19 23 25 29 ecc.ecc.

Definizione
Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma
1) X^2+6nX=NR
2) X^2+6nX+2X=NR
3) X^2+6nX+4X=NR
Dimostrazione
Dal lemma segue direttamente
1) X(X+6n)=NR
2) X(X+6n+2)=NR
3) X(X+6n+4)=NR

In più si può osservare che:
(6h+1)*(6k+1)=6G+1
(6h+5)*(6k+5)=6G+1
(6h+1)*(6k+5)=6G+5
(6h+5)*(6k+1)=6G+5
----------------------------------------------------------------------------------------
Da ciò si può dedurre che risolvendo (6h+1)*(6k+1)=6G+1 si possano risolvere gli altri tre casi
questi (6h+1)*(6k+5)=6G+5 (6h+5)*(6k+1)=6G+5 moltiplicando per 5
e questo (6h+5)*(6k+5)=6G+1 moltiplicando per 25

Quindi prendiamo come caso base
(6h+1)*(6k+1)=6G+1
X^2+6nX=NR
si può facilmente notare che
se G è pari n sarà pari
se G è dispari n sarà dispari
----------------------------------------------------------------------------------------
Se NR=(6*a+1)*(6*b+1)
allora possiamo scriverlo nella forma
NR=(6*a+1)^2+6*n*(6*a+1)
quindi
n=(G-6*a^2-2*a)/(6*a+1)
dove G=(NR-1)/6

----------------------------------------------------------------------------------------
Per capire ci scriviamo una tabella dove i valori NR=(6*a+1)^2+6*n*(6*a+1)
a parte da 1 ed n parte da 0

a\n
49 91 133 175 217 259 ….......
169 247 325 403 481 559 …......
361 475 589 703 817 931 …......
625 775 925 1075 1225 1375 …......
961 1147 1333 1519 1705 1891 ….......
1369 1591 1813 2035 2257 …................
…...............................................................
…...............................................................

Si può osservare che la differenza tra NR(a+1,n-2)-NR(a,n)=36*(n-1)

Quindi l'idea è di aggiungere ad NR un multiplo di 36

Cioè NR2=NR+i*36

fino a quando non soddisfi una determinata condizione cioè questa NR=(6*a+1)^2+6*n*(6*a+1) con (6*a+1) divisore di NR

calcolandoci la n dalle seguenti da una delle due
Se (NR-1)/6 è dispari
(2+2*N)*N/2-(2+2*M)*M/2=(NR2-NR1)/36=K dove n=2*N+1
Se (NR-1)/6 è pari
N^2-M^2=(NR2-NR1)/36=K dove n=2*N

[(*NOTA1*) per il momento tralascio come si calcola n ed m , ci devo pensare un po]

Quindi avremo n-1 possibilità di risolvere la fattorizzazione.

Da notare che più grande è i più la frequenza dei numeri che ci interessano è bassa.

Esempi

[(*NOTA2*) In questi esempi terremo conto che di solito in RSA il numero da fattorizzare NR=p*q avrà q/p < 2 ]

Esempio 1

617251=p*q=p^2+6*n*p

per la (*NOTA2*) p >= 553 e q <= 1111

quindi la n massima è n_max=(q-p)/6=93

i numeri i validi sono
84
(2+2*N)*N/2-(2+2*M)*M/2=84
N=42
n=2*42+1=85
617251=p^2+6*85*p
segue p=571

166
(2+2*N)*N/2-(2+2*M)*M/2=166
N=42
n=2*42+1=85

246
(2+2*N)*N/2-(2+2*M)*M/2=246
N=42
n=2*42+1=85

324
400
474
546
ecc.
ecc.

Esempio 2

620677=p*q=p^2+6*n*p

i numeri i validi sono
85
N^2-M^2=85
N=43
n=2*43=86
620677=p^2+6*86*p
segue p=571

ecc.
ecc.

Alberico Lepore 24 Agosto 2017

LaurV · 2017-09-05, 03:54

Wow! A wonderful algorithm. Can you please factor the following C154 number for me?

Code:

9244198061795738171803076086524911379752268769558126772679104427875162378559757802686251958103938360845772387320740454715805477545200393208224631568651017

If you find the factors fast, you save me the time to find a poly for it, to do sieving, filtering, LA, etc.

With O(k) you will only need few hours, instead of me spending a week or so...

Thanks in advance.

P.S. If you can not, then get the heck out of here, and stop polluting the forum with rubbish...

Max0526 · 2017-09-05, 19:43

@LaurV
On a serious note, do you need a (good) poly for this C154?

Dr Sardonicus · 2017-09-06, 13:13

Quote:

Originally Posted by jnml

PSA: Let me advise anyone against downloading the paper for at least two reasons: it has authors name in its title (cf. Batalov's post above) and downloading it requires to "connect" with the author on G+ or FB.

My reasoning was even briefer: The conjecture wasn't stated at the link where the post said it was. Therefore, as far as I was concerned, the poster was up to no good. I wasn't about to download a file just to find out what his purported conjecture was. Besides -- what was stated in the link given in the post seemed not to be leading anywhere interesting.

And so it is that I remain happily in ignorance of what the "k" signifies in the "O(k)" part of the purported conjecture

CRGreathouse · 2017-09-06, 14:29

Quote:

Originally Posted by Dr Sardonicus

And so it is that I remain happily in ignorance of what the "k" signifies in the "O(k)" part of the purported conjecture

Likewise, despite having read the material.

firejuggler · 2017-09-06, 14:34

you know, k,n,m,p x,y,z...... different country have different notation for the same think... log(n) , log(y), or sin(n) shouldn't phase you.

2017-08-30, 10:57	#1
Alberico Lepore May 2017 ITALY 2·3²·29 Posts	Lepore Factorization in O(k) Conjecture Lepore Factorization in O(k) Conjecture https://www.academia.edu/34408457/Le...O_k_Conjecture Do you think about it?

2017-09-05, 03:54	#7
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 282D₁₆ Posts	Wow! A wonderful algorithm. Can you please factor the following C154 number for me? Code: 9244198061795738171803076086524911379752268769558126772679104427875162378559757802686251958103938360845772387320740454715805477545200393208224631568651017 If you find the factors fast, you save me the time to find a poly for it, to do sieving, filtering, LA, etc. With O(k) you will only need few hours, instead of me spending a week or so... Thanks in advance. P.S. If you can not, then get the heck out of here, and stop polluting the forum with rubbish... Last fiddled with by LaurV on 2017-09-05 at 03:57

2017-09-05, 19:43	#8
Max0526 "Max" Jun 2016 Toronto 929 Posts	C154 poly? @LaurV On a serious note, do you need a (good) poly for this C154?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semi-prime factorization conjecture	Alberico Lepore	Alberico Lepore	7	2018-02-16 08:27
20th Test of primality and factorization of Lepore with Pythagorean triples	Alberico Lepore	Alberico Lepore	43	2018-01-17 15:55
18th Test of primality and factorization of Lepore in 5 * log_25 (N) (New Year's algorithm)	Alberico Lepore	Alberico Lepore	2	2018-01-01 21:31
14° Primality test and factorization of Lepore ( conjecture )	Alberico Lepore	Alberico Lepore	48	2017-12-30 09:43
Conjecture	devarajkandadai	Math	13	2012-05-27 07:38

2017-08-30, 16:28	#2
CRGreathouse Aug 2006 2²×3×499 Posts	I don't see either a conjecture or an algorithm there. But I have a conjecture of my own: any paper which spends more than half its length exploring the consequences of numbers being of the form 6n ± 1 is unlikely to make an algorithmic or number-theoretic breakthrough. I know my conjecture seems oddly specific, but I've seen it pretty often. (At least with half replaced with a more reasonable fraction like a tenth.)

2017-09-03, 09:26	#4
Alberico Lepore May 2017 ITALY 2×3²×29 Posts	Look this https://www.academia.edu/34339494/Fa...t%C3%A0_random And think this If we go to look directly, numbers with k <n elements the game is done. feedback please thank you

2017-09-03, 10:27	#6
Alberico Lepore May 2017 ITALY 20A₁₆ Posts	Fattorizzazione RSA di Lepore Complessità random Definizione Tutti i numeri NR escluso i multipli di 2 e di 3 si scrivono nella forma 6h+1 e 6h+5. Dimostrazione NR modulo 6 =1 -> 6h+1 NR modulo 6 =2 -> è multiplo di 2 NR modulo 6 =3 -> è multiplo di 3 NR modulo 6 =4 -> è multiplo di 2 NR modulo 6 =5 -> 6h+5 NR modulo 6 =0 -> è multiplo di 2 e di 3 Lemma Quindi partendo da 1 e facendo +4 e +2 si ha 1 5 7 11 13 17 19 23 25 29 ecc.ecc. Definizione Ogni numero NR escluso i multipli di 2 e di 3 si scrivono nella forma 1) X^2+6nX=NR 2) X^2+6nX+2X=NR 3) X^2+6nX+4X=NR Dimostrazione Dal lemma segue direttamente 1) X(X+6n)=NR 2) X(X+6n+2)=NR 3) X(X+6n+4)=NR In più si può osservare che: (6h+1)(6k+1)=6G+1 (6h+5)(6k+5)=6G+1 (6h+1)(6k+5)=6G+5 (6h+5)(6k+1)=6G+5 ---------------------------------------------------------------------------------------- Da ciò si può dedurre che risolvendo (6h+1)(6k+1)=6G+1 si possano risolvere gli altri tre casi questi (6h+1)(6k+5)=6G+5 (6h+5)(6k+1)=6G+5 moltiplicando per 5 e questo (6h+5)(6k+5)=6G+1 moltiplicando per 25 Quindi prendiamo come caso base (6h+1)(6k+1)=6G+1 X^2+6nX=NR si può facilmente notare che se G è pari n sarà pari se G è dispari n sarà dispari ---------------------------------------------------------------------------------------- Se NR=(6a+1)(6b+1) allora possiamo scriverlo nella forma NR=(6a+1)^2+6n(6a+1) quindi n=(G-6a^2-2a)/(6a+1) dove G=(NR-1)/6 ---------------------------------------------------------------------------------------- Per capire ci scriviamo una tabella dove i valori NR=(6a+1)^2+6n(6a+1) a parte da 1 ed n parte da 0 a\n 49 91 133 175 217 259 …....... 169 247 325 403 481 559 …...... 361 475 589 703 817 931 …...... 625 775 925 1075 1225 1375 …...... 961 1147 1333 1519 1705 1891 …....... 1369 1591 1813 2035 2257 …................ …............................................................... …............................................................... Si può osservare che la differenza tra NR(a+1,n-2)-NR(a,n)=36(n-1) Quindi l'idea è di aggiungere ad NR un multiplo di 36 Cioè NR2=NR+i36 fino a quando non soddisfi una determinata condizione cioè questa NR=(6a+1)^2+6n(6a+1) con (6a+1) divisore di NR calcolandoci la n dalle seguenti da una delle due Se (NR-1)/6 è dispari (2+2N)N/2-(2+2M)M/2=(NR2-NR1)/36=K dove n=2N+1 Se (NR-1)/6 è pari N^2-M^2=(NR2-NR1)/36=K dove n=2N [(NOTA1) per il momento tralascio come si calcola n ed m , ci devo pensare un po] Quindi avremo n-1 possibilità di risolvere la fattorizzazione. Da notare che più grande è i più la frequenza dei numeri che ci interessano è bassa. Esempi [(NOTA2) In questi esempi terremo conto che di solito in RSA il numero da fattorizzare NR=pq avrà q/p < 2 ] Esempio 1 617251=pq=p^2+6np per la (NOTA2) p >= 553 e q <= 1111 quindi la n massima è n_max=(q-p)/6=93 i numeri i validi sono 84 (2+2N)N/2-(2+2M)M/2=84 N=42 n=242+1=85 617251=p^2+685p segue p=571 166 (2+2N)N/2-(2+2M)M/2=166 N=42 n=242+1=85 246 (2+2N)N/2-(2+2M)M/2=246 N=42 n=242+1=85 324 400 474 546 ecc. ecc. Esempio 2 620677=pq=p^2+6np i numeri i validi sono 85 N^2-M^2=85 N=43 n=243=86 620677=p^2+686*p segue p=571 ecc. ecc. Alberico Lepore 24 Agosto 2017

2017-09-06, 14:34	#11
firejuggler "Vincent" Apr 2010 Over the rainbow 2²×7×103 Posts	you know, k,n,m,p x,y,z...... different country have different notation for the same think... log(n) , log(y), or sin(n) shouldn't phase you.