mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-10-19, 16:56   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

10608 Posts
Default P-1 question of curiosity

This is more a question of curiosity than anything else:

What happens if, say, EVERY prime factor of a specific composite Mersenne number was "very smooth" for P-1 testing? I.e. what if for some specific M_p, Prime95 sets the first bound B1, and it just so happens that every prime q dividing M_p is B1-smooth? Would the P-1 test detect that? Would it somehow fail to detect that? Would your computer blow up?
JuanTutors is offline   Reply With Quote
Old 2004-10-19, 17:46   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Every prime factor of M_p would appear in the output, that means P-1 would simply report M_p itself as the factor found.

Alex
akruppa is offline   Reply With Quote
Old 2004-10-19, 17:48   #3
dave_dm
 
May 2004

1208 Posts
Default

I don't know what Prime95 itself does but the p-1 algorithm can detect this, yes. Let the gcd at the end be d = gcd(a^X-1, n), where n is the number to be factored and X is the product of all prime powers < B1. When d=1 we fail to find a factor; when 1<d<n, we find a nontrivial factor.

You are talking about the case a^X=1 (mod p) for all p | n, i.e. a^X=1 (mod n), so this corresponds to d = n. If this happens, repeat the calculation with a lower B1 until you catch some but not all of the factors.

In practice, this situation won't arise unless you're trying to factor small numbers with a bad choice of B1.

The same principle applies to ecm.

Dave
dave_dm is offline   Reply With Quote
Old 2004-10-20, 04:37   #4
Olympia
 

22·52·59 Posts
Default Hi. Could you please Help?

Suppose that p>3 is an odd prime and that a is not equal to 1 mod p. Prove that if a^3 congruences 1 mod p, then p congruences 1 mod 3. Hint: what happens if you divide p-1 by 3? What does Fermat's little theorem says all about this?

Thank so much.

Olympia

Last fiddled with by Olympia on 2004-10-20 at 04:39
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A meaningless curiosity fivemack Aliquot Sequences 2 2016-01-17 07:44
Results Curiosity Gordon PrimeNet 1 2015-07-30 06:49
I see this as a bit of a mathematical curiosity... petrw1 Math 4 2015-07-19 02:33
A Curiosity R.D. Silverman GMP-ECM 4 2012-05-10 20:00
Curiosity ET_ Math 7 2004-02-13 17:36

All times are UTC. The time now is 07:56.


Sat Jul 2 07:56:17 UTC 2022 up 79 days, 5:57, 0 users, load averages: 1.48, 1.36, 1.32

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.

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