mersenneforum.org Primality test based on factorization of n^2+n+1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-04, 20:09 #1 carpetpool     "Sam" Nov 2016 22×83 Posts Primality test based on factorization of n^2+n+1 The primality tests for n if n^2-1 is factored 33.33% or higher are found here. What about the neoclassical tests for n? Suppose that n^3-1 is factored 33.33% or higher. Is there a way to prove n prime WITHOUT using ECPP? For example, is it possible to prove this prp (n) prime given the known factorization of n^3-1? I would supposed the neoclassical tests would be used, but I'm not sure. Any ideas? Thanks.
 2018-02-04, 21:35 #2 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23×283 Posts If you know all the prime factors of n^3-1, then you know all the factors of n-1. This is because n-1 | n^3-1. So you can use Lucas primality test to prove that n is prime. If the partial know factors of n^3-1 are exclusive to n-1 factors then it would seem intuitively irrelevant to the primality of n, unless you can find an association between the (extra) factors of n^m-1 and n. I doubt such association exits. Last fiddled with by a1call on 2018-02-04 at 21:48
 2018-02-04, 21:59 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23×283 Posts I could not find your reference to primality testing of n when n^2-1 is 1/3 factored. https://primes.utm.edu/prove/index.html Please provide a direct link.
2018-02-05, 00:20   #4
Batalov

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

268016 Posts

How about Williams, 1978 reference here?
Quote:
 Originally Posted by UTM pages See [Williams78] for the theory and examples of these techniques). But the cost in terms of mathematical complication is very high. So in practice adding a few terms such as n2+n+1 or n2-n+1 is rarely worth the effort.

2018-02-05, 05:19   #5
carpetpool

"Sam"
Nov 2016

1010011002 Posts

Quote:
 Originally Posted by [B UTM Pages[/B]]The way Williams and others began in the 70's was to use the factors of other polynomials of n such as n2+1, n2+n+1 and n2-n+1 [Williams78].
Does the reference state when it is applicable though or exactly what theorems to follow? (Namely when a known factor of n^2+n+1 is roughly the size of n or greater). For constructing these n (which are prps or primes)

first choose a (proven) prime p = 1 (mod 3) and let a be a primitive root mod p.

compute m = a^((p-1)/3) mod p

If this m is (probably) prime, then most likely it can be proved using the fact that p is roughly the size of m (if not greater), and p divides m^3-1.

If this m is not prime, then choose some other prime q (can be small), and try and see if

m = a^((q-1)*((p-1)/3)) mod (q*p)

is (probably) prime. If so, then no need to continue further. If not try and find the smallest k such

m = a^((q-1)*q^(k-1)*((p-1)/3)) mod (q^k*p)

is (probably) prime.

For a quick demonstation of a another probable prime n (which may be proved prime based on the factorization of n^3-1 (and more specifically n^2+n+1).

First we have p = 13 and 6 a primitive root mod p (a = 19).

We find that 19^((p-1)/3) mod p isn't prime so we choose another prime q = 7.

Jumping ahead to step 2 (plus a little more work applied) we find that

m = a^(4*7^321) mod (7^322*13) is prp (already shown prime) and m^2+m+1 is 50% factored (33.33% for m^3-1). A proof based on factorization of m^2+m+1 would be easy to do for this m.

Last fiddled with by carpetpool on 2018-02-05 at 05:22

 2018-02-05, 05:20 #6 carpetpool     "Sam" Nov 2016 22·83 Posts @a1call: https://primes.utm.edu/prove/prove3_1.html https://primes.utm.edu/prove/prove3_2.html https://primes.utm.edu/prove/prove3_3.html Hope you find these useful.

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 43 2018-01-17 15:55 Alberico Lepore Alberico Lepore 2 2018-01-01 21:31 Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 Alberico Lepore Alberico Lepore 26 2017-12-17 18:44 Unabomber Math 1 2014-04-04 20:19

All times are UTC. The time now is 04:53.

Thu Jun 30 04:53:19 UTC 2022 up 77 days, 2:54, 0 users, load averages: 1.94, 1.55, 1.47

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.

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