mersenneforum.org  

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

Reply
 
Thread Tools
Old 2017-12-20, 17:27   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

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).
CRGreathouse is offline   Reply With Quote
Old 2017-12-21, 02:56   #13
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100110010111102 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
What do you think?
SSDD
Batalov is offline   Reply With Quote
Old 2017-12-21, 14:41   #14
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

CRGreathouse if i post the solution in O (log (N)) you promise me that if you find it interesting,you implement it?
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 14:53   #15
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

you implememt it?
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 16:59   #16
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

22·7·173 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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
ET_ is offline   Reply With Quote
Old 2017-12-21, 17:12   #17
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

20A16 Posts
Default

Quote:
Originally Posted by ET_ View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 17:28   #18
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-12-21, 17:33   #19
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2×32×29 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 18:23   #20
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2×32×29 Posts
Default

now it's okay
16° Primality test and factorization of Lepore
Attached Files
File Type: pdf 16° Primality test and factorization of Lepore.pdf (31.7 KB, 156 views)
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 18:39   #21
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

2·32·29 Posts
Default

we miss a passage that I'm studying
in a while I post it
Alberico Lepore is offline   Reply With Quote
Old 2017-12-21, 18:52   #22
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

52210 Posts
Default

now is correct
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primality test based on factorization of n^2+n+1 carpetpool Miscellaneous Math 5 2018-02-05 05:20
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
Factorization and primality test O([log_9(N)]^3) Alberico Lepore Alberico Lepore 26 2017-12-17 18:44
Lepore Factorization in O(k) Conjecture 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

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔