## RE: [PrimeNumbers] Asymmetry in splitting power of ordinates in P+1-alike

Expand Messages
• ... Subgroup of Mod x^2+1 (Gaussian integers) Mod N (obviously). ... I was going to look at higher dementions after this. :-I I was just trying to strip away
Message 1 of 5 , Jan 30, 2003
• 0 Attachment
--- Paul Leyland <pleyland@...> wrote:
> > I was just mucking around with some weird groups trying to
> > see if I could
> > improve on William's P+1, and I noticed that in one of my
> > groups I had the
> > choice of either checking gcd(N,x_i-1) _or_ gcd(N, y_i) for
> > factors, where
> > < x_i, y_i > is a point in my group (and <1,0> is my I)
>
> Fascinating. Which group are you using?

Subgroup of
Mod x^2+1 (Gaussian integers)
Mod N (obviously).

> I've been playing around with commutative hypercomplex numbers for the last couple of weeks.
> These are like quaternions, but commutative and i^2 = j^2 = -k^2 = 1. They do *not* form a
> division algebra.

I was going to look at higher dementions after this. :-I

I was just trying to strip away the 'try both x and y' fluff from my gp
script to include here, and I think may have broken it! Having said that, I
should probably keep that stuff in so that my bias can be demonstrated.

> I also played a bit with the 2-d algebra defined by i*i = 1. Again, not a division algebra.

I've heard the term in a context of Clifford Algebras, but know very little about them
(I can construct them - double the previous size, and add a twist). I know
IDs, EDs, and UFDs though, is it an alias for one of those?

> Because these things don't form a field, it would seem to be possible to exploit zero divisors
> in a factoring algorithm. Not got very far yet.

It's an interesting concept. I've not convinced myself that the zero-divisors
help find factors though. However, in this field it's worth throwing any idea
around. Hmmm, no, scratch that, I think I have convinced myself. I think I
like it. However, I oughtn't get distracted from my little gaussian babies
until I've got something fluff-free.

Phil

=====
Is that free as in Willy or as in bird?

__________________________________________________
Do you Yahoo!?
http://mailplus.yahoo.com
• ... The group table for this algebra is straightforward: * | 1 i -1 -i ... 1 | 1 i -1 -i i | i 1 -i -1 -1 | -1 -i 1 i -i | -i 1 i 1 Clearly an
Message 2 of 5 , Jan 30, 2003
• 0 Attachment
> > I also played a bit with the 2-d algebra defined by i*i =
> 1. Again, not a division algebra.
>
> I've heard the term in a context of Clifford Algebras, but
> know very little about them
> (I can construct them - double the previous size, and add a
> twist). I know
> IDs, EDs, and UFDs though, is it an alias for one of those?

The group table for this algebra is straightforward:

* | 1 i -1 -i
---+------------
1 | 1 i -1 -i
i | i 1 -i -1
-1 | -1 -i 1 i
-i | -i 1 i 1

Clearly an abelian group.

You can easily form a commutative ring with unit from it.
A typical element X looks like x+iy but the difference from
the field C is that X^(-1) is (x-iy)/(x^2-y^2), and X is a divisor
of zero when x = \pm y.

I rather suspect that the P-1 analog in this ring is just the P+1 algorithm, but haven't yet proved that.

Paul
• ... What s your b_0? If it s real you stay real, and end up doing P-1. If it s imaginary , you become real upon the first squaring, and P-1 ensues So I
Message 3 of 5 , Jan 30, 2003
• 0 Attachment
--- Paul Leyland <pleyland@...> wrote:
> The group table for this algebra is straightforward:
>
> * | 1 i -1 -i
> ---+------------
> 1 | 1 i -1 -i
> i | i 1 -i -1
> -1 | -1 -i 1 i
> -i | -i 1 i 1
>
> Clearly an abelian group.
>
> You can easily form a commutative ring with unit from it.
> A typical element X looks like x+iy but the difference from
> the field C is that X^(-1) is (x-iy)/(x^2-y^2), and X is a divisor
> of zero when x = \pm y.
>
> I rather suspect that the P-1 analog in this ring is just the P+1 algorithm, but haven't yet
> proved that.

If it's 'real' you stay real, and end up doing P-1.
If it's 'imaginary', you become real upon the first squaring, and P-1 ensues
So I assume you're 'complex'.

Do you agree with these power tables for (1+2i), which I chose arbitrarily?

(15:31) gp > v=init(7)
%5 = [Mod(1, 7), Mod(2, 7)]
(15:38) gp > for(i=0,15,print(i" "pow(v,i)))
0 [1, 0]
1 [Mod(1, 7), Mod(2, 7)]
2 [Mod(5, 7), Mod(4, 7)]
3 [Mod(6, 7), Mod(0, 7)]
4 [Mod(6, 7), Mod(5, 7)]
5 [Mod(2, 7), Mod(3, 7)]
6 [Mod(1, 7), Mod(0, 7)]
7 [Mod(1, 7), Mod(2, 7)]

O(v mod 7) = 6

(15:38) gp > v=init(11)
%6 = [Mod(1, 11), Mod(2, 11)]
(15:41) gp > for(i=0,15,print(i" "pow(v,i)))
0 [1, 0]
1 [Mod(1, 11), Mod(2, 11)]
2 [Mod(5, 11), Mod(4, 11)]
3 [Mod(2, 11), Mod(3, 11)]
4 [Mod(8, 11), Mod(7, 11)]
5 [Mod(0, 11), Mod(1, 11)]
6 [Mod(2, 11), Mod(1, 11)]
7 [Mod(4, 11), Mod(5, 11)]
8 [Mod(3, 11), Mod(2, 11)]
9 [Mod(7, 11), Mod(8, 11)]
10 [Mod(1, 11), Mod(0, 11)]
11 [Mod(1, 11), Mod(2, 11)]

O(v mod 11) = 10

If so, then:

O(v mod 3)=2
O(v mod 5)=4
O(v mod 7)=6
O(v mod 11)=10
O(v mod 13)=6
O(v mod 17)=16
O(v mod 19)=18
O(v mod 23)=22
O(v mod 29)=28
O(v mod 31)=30
O(v mod 37)=18
O(v mod 41)=8
O(v mod 43)=42
O(v mod 47)=46
O(v mod 53)=52
O(v mod 59)=58
O(v mod 61)=10
O(v mod 67)=22
O(v mod 71)=70
O(v mod 73)=12
O(v mod 79)=78
O(v mod 83)=82
O(v mod 89)=88
O(v mod 97)=48

Which looks like p-1.

I tried with other initial values (1+3i, 1+4i, etc.) and they all came out
with orders dividing p-1.
I also tried bases 2p with p=prime, and ditto. Likewise 3p.

Phil

=====
Is that free as in Willy or as in bird?

__________________________________________________
Do you Yahoo!?