mersenneforum.org > Math Mod question in N-1 primality test
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2023-02-04, 07:29 #1 wblipp     "William" May 2003 Near Grandkid 2·1,187 Posts 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?
 2023-02-04, 13:07 #2 charybdis     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.
 2023-02-09, 11:52 #3 henryzz Just call me Henry     "David" 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.
2023-02-09, 13:16   #4
charybdis

Apr 2020

94910 Posts

Quote:
 Originally Posted by henryzz 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

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 a1call Miscellaneous Math 29 2018-12-24 01:42 Trilo Miscellaneous Math 25 2018-03-11 23:20 Citrix Math 3 2005-09-19 15:06 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

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.

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