mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2017-08-30, 10:57   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1111110002 Posts
Default 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?
Alberico Lepore is offline  
Old 2017-08-30, 16:28   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

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.)
CRGreathouse is offline  
Old 2017-08-31, 00:19   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

17·563 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.)
Batalov is offline  
Old 2017-09-03, 09:26   #4
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

50410 Posts
Default

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
Alberico Lepore is offline  
Old 2017-09-03, 10:24   #5
jnml
 
Feb 2012
Prague, Czech Republ

2648 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.

Last fiddled with by jnml on 2017-09-03 at 10:25 Reason: s/reazons/reasons/, s/it's/its/
jnml is offline  
Old 2017-09-03, 10:27   #6
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1111110002 Posts
Default

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
Alberico Lepore is offline  
Old 2017-09-05, 03:54   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

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
LaurV is offline  
Old 2017-09-05, 19:43   #8
Max0526
 
"Max"
Jun 2016
Toronto

38A16 Posts
Default C154 poly?

@LaurV
On a serious note, do you need a (good) poly for this C154?
Max0526 is offline  
Old 2017-09-06, 13:13   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

4,999 Posts
Default

Quote:
Originally Posted by jnml View Post
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
Dr Sardonicus is offline  
Old 2017-09-06, 14:29   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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.
CRGreathouse is offline  
Old 2017-09-06, 14:34   #11
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

22×3×13×17 Posts
Default

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.
firejuggler is online now  
Closed Thread

Thread Tools


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

All times are UTC. The time now is 17:05.


Sun Oct 24 17:05:40 UTC 2021 up 93 days, 11:34, 0 users, load averages: 1.09, 1.27, 1.29

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