mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-04-09, 01:38   #1
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

12418 Posts
Lightbulb 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?
Stargate38 is offline   Reply With Quote
Old 2012-04-09, 11:46   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2012-04-09, 14:16   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

125710 Posts
Default

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
File Type: txt the attachment.txt (785 Bytes, 161 views)

Last fiddled with by Raman on 2012-04-09 at 14:21
Raman is offline   Reply With Quote
Old 2012-04-10, 01:24   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by Raman View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2012-04-10, 04:20   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

Quote:
Originally Posted by Raman View Post
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
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Finding multiples of a real number that are close to a whole number mickfrancis Math 16 2017-03-01 07:17
Basic Number Theory 10: complex numbers and Gaussian integers Nick Number Theory Discussion Group 8 2016-12-07 01:16
Basic Number Theory 11: Gaussian primes Nick Number Theory Discussion Group 0 2016-12-03 11:42
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35
Largest number in the real universe danjmi Science & Technology 17 2004-09-26 20:25

All times are UTC. The time now is 11:37.


Mon Oct 18 11:37:17 UTC 2021 up 87 days, 6:06, 0 users, load averages: 0.82, 1.11, 1.31

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