 mersenneforum.org Using quarternions instead of Gaussian primes when factoring a real number?
 Register FAQ Search Today's Posts Mark Forums Read 2012-04-09, 01:38 #1 Stargate38   "Daniel Jackson" May 2011 14285714285714285714 10111101002 Posts Using quarternions instead of Gaussian primes when factoring a real number? Do you think this would be efficient? It works. Here's a multiplication table and some factorizations: Code:  1 i j k 1 1 i j k i i -1 k -j j j -k -1 i k k j -i -1 911=(30+3i+j+k)*(30-3i-j-k) 569=(5+12i+12j+16k)*(5-12i-12j-16k) Here's how I did it: 569=5^2+12^2+12^2+16^2=13^2+20^2 911=30^2+3^2+1^2+1^2 There is more than one way to factor these numbers: (30+3i+3j+3k)*(30-3i-3j-3k)=911=(30-3i+3j+3k)*(30+3i-3j-3k) Gaussian primes are the sum of 4 squares (with the exception of 3 which is 1^2+1^2+1^2), so they have 24 different quarternion factorizations each: p=(a±bi±cj±dk)*(a±bi±cj±dk) where the signs are opposite (as in the example with 911). What do you think?   2012-04-09, 11:46   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts Quote:
 Originally Posted by Stargate38 Do you think this would be efficient? It works. Here's a multiplication table and some factorizations: Code:  1 i j k 1 1 i j k i i -1 k -j j j -k -1 i k k j -i -1 911=(30+3i+j+k)*(30-3i-j-k) 569=(5+12i+12j+16k)*(5-12i-12j-16k) Here's how I did it: 569=5^2+12^2+12^2+16^2=13^2+20^2 911=30^2+3^2+1^2+1^2 There is more than one way to factor these numbers: (30+3i+3j+3k)*(30-3i-3j-3k)=911=(30-3i+3j+3k)*(30+3i-3j-3k) Gaussian primes are the sum of 4 squares (with the exception of 3 which is 1^2+1^2+1^2), so they have 24 different quarternion factorizations each: p=(a±bi±cj±dk)*(a±bi±cj±dk) where the signs are opposite (as in the example with 911). What do you think?
You are aware that the Quaternions (e.g. a Quaternion ring) are not commutative????

Get back to use after you get a degree in mathematics. Then your posts
may start to make sense. You bandy about words such as "efficient"
with no clue what the words mean.   2012-04-09, 14:16   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts Given away the values for 3b (mod N), 3a (mod N), b > a
we do not know the values for b, a directly at all

Can we calculate the value for 3b mod a mod N efficiently?
Attached Files the attachment.txt (785 Bytes, 211 views)

Last fiddled with by Raman on 2012-04-09 at 14:21   2012-04-10, 01:24   #4
CRGreathouse

Aug 2006

5,987 Posts Quote:
 Originally Posted by Raman Given away the values for 3b (mod N), 3a (mod N), b > a we do not know the values for b, a directly at all Can we calculate the value for 3b mod a mod N efficiently?
If 3^a = 6 mod 101 and 3^b = 91 mod 101, is 3^(b mod a) 32 or 39 mod 101? It depends on what a and b are. So you can't compute this at all, let alone efficiently.   2012-04-10, 04:20   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts Quote:
 Originally Posted by Raman If we could be able to do that instantly, then we will be able to factor N quite quickly. Starting away right with the values for u = 3^Phi(N) = 1 (mod N) v = 3^N mod N. Since that if GCD(Phi(N), N) = 1, whether believing it, then we could be able to calculate the step-by-step ladder for the values for 3^(u mod v) mod N, 3^(v mod u) mod N, alternatively, similar to the GCD calculation process. And then reverse the direction starting away right directly from the value for the 3^0 = 1 (mod N), 3^GCD(Phi(N), N) mod N, to get the intermediate exponents, and then ultimately the value for Phi(N)
If instead of 3, some other generator element, then... ?
Oops! But that we do not know beforehand itself if whether an element is a generator, on over the ring Zn* at all
But that it is being possible to randomly choose a base, there are being 50% chances, turns, for it to be the primitive root...

3b-a mod N = (3b)(3a)-1 mod N
But that how do we know that how many times we have to carry out the above mentioned subtraction process before itself

Last fiddled with by Raman on 2012-04-10 at 05:08  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mickfrancis Math 16 2017-03-01 07:17 Nick Number Theory Discussion Group 8 2016-12-07 01:16 Nick Number Theory Discussion Group 0 2016-12-03 11:42 troels munkner Miscellaneous Math 4 2006-06-02 08:35 danjmi Science & Technology 17 2004-09-26 20:25

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

Thu Feb 9 06:16:51 UTC 2023 up 175 days, 3:45, 1 user, load averages: 0.60, 0.67, 0.84 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.

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