Go Back > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Thread Tools
Old 2023-02-04, 07:29   #1
wblipp's Avatar
May 2003
Near Grandkid

2·1,187 Posts
Default Mod question in N-1 primality test

The classic paper on N+/-1 primality tests is Brillhart, Lehmer, and Selfridge 1975. I need help understanding part of Remark 4 of Theorem 5.

At this point N-1 has been partially factored as F*R, with F fully factored. We know from a previous theorem that if N is composite, it is (c*F+1)*(d*F+1). Part of Remark 4 says that if N = -1 (mod 5) and it is known that 5 is a quadratic residue of N, then since 5 does not divide F, 5 divides c*d.

I think this should be understood as meaning "5 divides c*d*F". But why?

When working mod 5, you can get -1 from 2*2 or 3*3 in addition to 1*(-1) and (-1)*1, so you can't just say one of the factors is 1 (mod 5). The "known to be a quadratic residue" must be useful somehow, but how?
wblipp is offline   Reply With Quote
Old 2023-02-04, 13:07   #2
charybdis's Avatar
Apr 2020

13·73 Posts

If 5 is a quadratic residue mod N, then it is also a quadratic residue mod each of the factors of N. But (5|cF+1) = (cF+1|5) by quadratic reciprocity, so if cF+1 is not a square mod 5 (i.e. it is 2 or 3 mod 5), then 5 is not a square mod cF+1. Same goes for dF+1.

Note this doesn't assume cF+1 and dF+1 are prime: quadratic reciprocity holds for Jacobi symbols, and the Jacobi symbol (m|n) = -1 still implies m is not a quadratic residue mod n.
charybdis is offline   Reply With Quote
Old 2023-02-09, 11:52   #3
Just call me Henry
henryzz's Avatar
Sep 2007
Liverpool (GMT/BST)

23×757 Posts

Am I being brain-dead or is there a potential factorisation method here(not necessarily a good one)?

For composite N find factors of N-1 that satisfy Theorem 4.
These factors make up the fully factored part F.
We know that N = (c*F+1)*(d*F+1) but don't know c and d.
Now find a list of primes that N = -1 (mod p) and p is a quadratic residue of N.
These primes divide c*d and can be used to help find c and d.
If we have c and d we have a factorisation of N.

Potential problems:
This method will be easier with large F. Note F will always be less than sqrt(N) as otherwise, N will be prime.
No factors can be found that are smaller than F.
Determining if p is a quadratic residue of N is pretty much impossible without knowing the factors of N. Primes could be found by squaring numbers modulo N but N is unlikely to be -1 mod p.
It may be difficult to find factors of N-1.
The number of primes that we can determine of factors of c*d may too small to make finding c and d possible.

It looks like this method stands a vague chance of working on numbers generated such that there are many known factors of N-1 and primes that are quadratic residues of N and N = -1 mod p.
Is it possible to generate numbers where N-1 and N+1 have many known factors and the prime factors of N+1 are quadratic residues mod N? Note that knowing factors of x*N+1 meeting these conditions is sufficient.

It is worth noting that if we can find numbers that are probably factors of c*d then these could be used as prompts for the P-1 method.

This is probably completely useless but there may be someone interested.
henryzz is offline   Reply With Quote
Old 2023-02-09, 13:16   #4
charybdis's Avatar
Apr 2020

94910 Posts

Originally Posted by henryzz View Post
Am I being brain-dead or is there a potential factorisation method here(not necessarily a good one)?

For composite N find factors of N-1 that satisfy Theorem 4.
One of the conditions of Theorem 4 is that N is a pseudoprime to base ai. How do you propose to find such a base without knowing the factorization of N?

Last fiddled with by charybdis on 2023-02-09 at 13:47 Reason: removed some rubbish
charybdis is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
+/- 6 Primality Test a1call Miscellaneous Math 29 2018-12-24 01:42
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
N-1 primality test Citrix Math 3 2005-09-19 15:06
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 16:30.

Wed Mar 29 16:30:23 UTC 2023 up 223 days, 13:58, 0 users, load averages: 0.91, 1.03, 1.06

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

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