mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2009-07-05, 00:22   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

22·7·112 Posts
Default question

Its not really homework, just something I'm wondering about.

Given 2 primes p and q I want to find the smallest k>0 so (2*k*p+1) = 0 (mod q)

Is there any faster way than trying all k from 1 until you find one that works?

Last fiddled with by ATH on 2009-07-05 at 00:22
ATH is offline   Reply With Quote
Old 2009-07-05, 03:49   #2
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

I helieve you use the Extended Euclidean Algorithm.
davieddy is offline   Reply With Quote
Old 2009-07-05, 17:53   #3
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

194A16 Posts
Default

Hope to spare you the indignities I suffered when I asked
the same question for the same reason

http://mersenneforum.org/showthread.php?t=9700

David
davieddy is offline   Reply With Quote
Old 2009-07-06, 00:41   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

338810 Posts
Default

Thanks, it was just something like this I was looking for:

(2kp+1)=0 (mod q) => 2kp+1= c*q => c*q - 2kp = 1

Then I can find c and more importantly -2*k my using the algorithm on GCD(p,q). Allready tested it and it works great.

Last fiddled with by ATH on 2009-07-06 at 00:52
ATH is offline   Reply With Quote
Old 2009-07-06, 07:41   #5
davieddy
 
davieddy's Avatar
 
"Lucan"
Dec 2006
England

2·3·13·83 Posts
Default

Quote:
Originally Posted by ATH View Post
Thanks, it was just something like this I was looking for:

(2kp+1)=0 (mod q) => 2kp+1= c*q => c*q - 2kp = 1

Then I can find c and more importantly -2*k my using the algorithm on GCD(p,q). Allready tested it and it works great.
If you did GCD(2p,q) you'd get -k. Is this any improvement?

I see Davar55 has revived that embarrassing thread I cited in
the Math forum!

Last fiddled with by davieddy on 2009-07-06 at 07:42
davieddy is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 19:13.


Wed Oct 5 19:13:40 UTC 2022 up 48 days, 16:42, 0 users, load averages: 1.38, 1.27, 1.18

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.

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