 mersenneforum.org 14° Primality test and factorization of Lepore ( conjecture )
 Register FAQ Search Today's Posts Mark Forums Read  2017-12-20, 17:27 #12 CRGreathouse   Aug 2006 597910 Posts If it's not a factorization algorithm that would explain why you seem to start with a factorization (which of course you can't do when you don't yet know it).   2017-12-21, 02:56   #13
Batalov

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

100110010111102 Posts Quote:
 Originally Posted by Alberico Lepore What do you think?
SSDD   2017-12-21, 14:41 #14 Alberico Lepore   May 2017 ITALY 2·32·29 Posts CRGreathouse if i post the solution in O (log (N)) you promise me that if you find it interesting,you implement it?   2017-12-21, 14:53   #15
Alberico Lepore

May 2017
ITALY

2·32·29 Posts you implememt it?
Attached Files 15° Primality test and factorization of Lepore O(log_2()).pdf (32.4 KB, 152 views)   2017-12-21, 16:59   #16
ET_
Banned

"Luigi"
Aug 2002
Team Italia

22·7·173 Posts Quote:
 Originally Posted by Alberico Lepore you implememt it?
I still can't understand (my fault...) what you are trying to conjecture.

a) Factorisation?
b) A hard way to write N=187?
c) A generalization in writing a subclass of polynomials having the same behavio(u)r? (and in this case, what is such behavio(u)r?

In other, simpler words, what should your conjecture demonstrate?

Feel free to answer in Italian if you feel more apt to do it.

Last fiddled with by ET_ on 2017-12-21 at 17:01   2017-12-21, 17:12   #17
Alberico Lepore

May 2017
ITALY

20A16 Posts Quote:
 Originally Posted by ET_ I still can't understand (my fault...) what you are trying to conjecture. a) Factorisation? b) A hard way to write N=187? c) A generalization in writing a subclass of polynomials having the same behavio(u)r? (and in this case, what is such behavio(u)r? In other, simpler words, what should your conjecture demonstrate? Feel free to answer in Italian if you feel more apt to do it.
(a)Fattorizzazione
Effettivamente è tutto dimostrabile
solo che non sono pratico con la complessità computazionale che a me sembra log_2()

Ah c'è un piccolo errore bisogna testare anche il 19   2017-12-21, 17:28   #18
CRGreathouse

Aug 2006

3·1,993 Posts Quote:
 sqrt[X+2*(X/9)^2+X+((X/9-9)/2)^2]=sqrt[N-n*a] , X=3*K Testing K=1,3,5,7,9,11,13,15,17
I take this to mean: test successive odd values of K, starting at 1, in the first equation via the second equation.

Letting K = 2m+1 the first equation becomes

sqrt[3(2m+1)+2*(3(2m+1)/9)^2+3(2m+1)+((3(2m+1)/9-9)/2)^2] = sqrt[N-n*a]

which can be simplified to

sqrt((m + 5)^2) = sqrt[N-n*a]

and so presumably

(m + 5)^2 = N - n*a

where N is the number we're trying to factor, a is some factor of N, and n = N/a - a. Now let's use that last equation to simplify the right side:

(m + 5)^2 = N - (N/a - a)*a
(m + 5)^2 = N - (N - a^2)
(m + 5)^2 = a^2
m + 5 = ±a

So your method is just checking numbers m + 5 until they divide N. This is a primitive version of trial division and its running time (with schoolbook division) is O(sqrt(n)*log(n)^2), exponentially slower than you suggest.   2017-12-21, 17:33   #19
Alberico Lepore

May 2017
ITALY

2×32×29 Posts Quote:
 Originally Posted by CRGreathouse I take this to mean: test successive odd values of K, starting at 1, in the first equation via the second equation. Letting K = 2m+1 the first equation becomes sqrt[3(2m+1)+2*(3(2m+1)/9)^2+3(2m+1)+((3(2m+1)/9-9)/2)^2] = sqrt[N-n*a] which can be simplified to sqrt((m + 5)^2) = sqrt[N-n*a] and so presumably (m + 5)^2 = N - n*a where N is the number we're trying to factor, a is some factor of N, and n = N/a - a. Now let's use that last equation to simplify the right side: (m + 5)^2 = N - (N/a - a)*a (m + 5)^2 = N - (N - a^2) (m + 5)^2 = a^2 m + 5 = ±a So your method is just checking numbers m + 5 until they divide N. This is a primitive version of trial division and its running time (with schoolbook division) is O(sqrt(n)*log(n)^2), exponentially slower than you suggest.
thank you
I get better   2017-12-21, 18:23   #20
Alberico Lepore

May 2017
ITALY

2×32×29 Posts now it's okay
16° Primality test and factorization of Lepore
Attached Files 16° Primality test and factorization of Lepore.pdf (31.7 KB, 156 views)   2017-12-21, 18:39 #21 Alberico Lepore   May 2017 ITALY 2·32·29 Posts we miss a passage that I'm studying in a while I post it   2017-12-21, 18:52   #22
Alberico Lepore

May 2017
ITALY

52210 Posts now is correct
Attached Files 16° Primality test and factorization of Lepore (correct).pdf (34.0 KB, 169 views)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2018-02-05 05:20 Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 Alberico Lepore Alberico Lepore 26 2017-12-17 18:44 Alberico Lepore Alberico Lepore 61 2017-09-23 21:52

All times are UTC. The time now is 21:48.

Thu May 19 21:48:24 UTC 2022 up 35 days, 19:49, 1 user, load averages: 2.30, 1.97, 1.78