Lepore Factorization in O(k) Conjecture
 

Lepore Factorization in O(k) Conjecture

[url]https://www.academia.edu/34408457/Lepore_Factorization_in_O_k_Conjecture[/url]

Do you think about it?

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.)

[QUOTE=Alberico Lepore;466666]
[url]https://www.academia.edu/34408457/Lepore_Factorization_in_O_k_Conjecture[/url]

Do you think about it?[/QUOTE]
[QUOTE]Page Not Found
Sorry. We can't find the page you're looking for.[/QUOTE]

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.)

Look this

[url]https://www.academia.edu/34339494/Fattorizzazione_RSA_di_Lepore_Complessit%C3%A0_random[/url]

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

feedback please

thank you

[QUOTE=Alberico Lepore;466969]Look this

[url]https://www.academia.edu/34339494/Fattorizzazione_RSA_di_Lepore_Complessit%C3%A0_random[/url]

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

feedback please

thank you[/QUOTE]

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.

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

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

[CODE]9244198061795738171803076086524911379752268769558126772679104427875162378559757802686251958103938360845772387320740454715805477545200393208224631568651017[/CODE]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...

C154 poly?
 

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

[QUOTE=jnml;466974]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.[/QUOTE]
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 [i]about[/i] to download a file just to find out what his purported conjecture was. Besides -- what [i]was[/i] 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
:smile:

[QUOTE=Dr Sardonicus;467262]And so it is that I remain happily in ignorance of what the "k" signifies in the "O(k)" part of the purported conjecture[/QUOTE]

Likewise, despite having read the material. :down:

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.