Re: FLTMA: A little group theory


Chip Eastham wrote:
The Dougster wrote:
There is a probem with FLTMA1.exe, at
ftp://users.aol.com/DGoncz/Education/NVCC.

I compute a quotient, then take the power. It doesn't work out.

I call the quotients qxiyz for quotient of x divided by y mod z,
qyixz similarly, and so qzixy and qxiyx. I call the inverse y mod z
iyz, and so
ixz, ixy, and iyx.

I find (x * iyz)^n mod z =/= qxiyz^n mod z

I was confused about how Chip Eastham got to (x/y)^n == -1 mod z but it
seemed right, and I think I understand it now, but working out y * iyz
= 1 mod z to solve for iyz, and computing qxiyz = (x * iyz) mod z
before looking at the powers qxiyz^n mod z just doesn't seem to work.

Have I made one too many substitutions and lost the validity of the
modular arithmetic?

Most likely it's a typo but I am not seeing it.

I am investigating this.


A couple of points. First, for some values of x,y,z there
will not be a solution for (x/y)^n = -1 mod z, so your code
will have to report these failures "nicely". This contrasts
with congruences (z/y)^n = 1 mod x and (z/x)^n = 1 mod y
which are always solvable, resp. by some divisors of
phi(x) and phi(y). Ie. elements of a multiplicative group
must have an order.

-1 mod z = z-1 is always coprime to z so this element always exists in
the group, and by theorem 4.16 in Fraleigh, every "linear" equation
ax=b and ya=b in an arbitrary group G has unique solutions x and y in
G, but this equation with w = z/y is w*w = -1 which is not a linear
equation, or w*(w*w) = -1 but I do see that there is some way this
equation w^n = -1 mod z might have no solution. I have to think about
this, but I have already programmed it.

What I noted about cases when (x/y)^n = -1 mod z does
have a solution is that then n is half the order of (x/y) in
Z/zZ*.

Um, in a post elsewhere in sci.math, I think we determined that if
(x/y)^n = 1 mod z then (x/y)^m = -1 mod z, where m divides n. Or
something like that. So if n is prime, we have no solution for m. Maybe
that's the deal.

The converse is not true, though. Consider the residue
in Z/15Z. The order of residue 4 is 2, but clearly half that
order does not give a power of 4 equal to -1 in Z/15Z.
In fact you can run through all possible powers of 4 in
Z/15Z without getting to -1.

That follows from 2 prime, I think, if the above was valid.


So my recommendation for solving (x/y)^n = -1 mod z
is to compute the order of (x/y) in Z/zZ* just as you
would for the other two congruences. If this order is
not even, you are done in that there is no solution.
If the order is even, you must verify whether or not
half the order gives (x/y)^n = -1 mod z.

I will investigate.

Finally we have three simultaneous congruences
for the exponents n (assuming the third condition
here can be satisfied at all):

n is a multiple of the order of (z/y) in Z/xZ*
n is a multiple of the order of (z/x) in Z/yZ*
n is an odd multiple of half the order of (x/y)
in Z/zZ* (if a solution exists)

Something very close to that, if m divides n, which I think I've seen
in tests.

Doug

.

Relevant Pages

  • Re: FLTMA: A little group theory
    ... I compute a quotient, then take the power. ... order does not give a power of 4 equal to -1 in Z/15Z. ... n is a multiple of the order of in Z/xZ* ...
    (sci.math)
  • Re: |[IRL] Didnt we already win this fight?
    ... the government (welfare, unemployment insurance, whatever) because I'm ... Health insurance (at least until we have some sort of sane single ... I think that multiple marriage has acquired a bad reputation because ... women with a reasonably equitable power balance in a committed, ...
    (rec.games.frp.dnd)
  • Re: Is the BBC deliberately degrading FM?
    ... You are comparing apples to oranges. ... If you use multiple parallel ... guard bands is not inefficient. ... Note that that is AVERAGE power ...
    (alt.radio.digital)
  • Re: Is the BBC deliberately degrading FM?
    ... You are comparing apples to oranges. ... If you use multiple parallel ... Sorry, but you're just looking for excuses because you said that OFDM "IS inarguably inefficient", when in fact OFDM is nothing of the sort, ... has identical average power efficiency to 8-VSB with the same error correct ...
    (alt.radio.digital)
  • Re: [PATCH] Remove some divide instructions
    ... Apparently cc-ing linux-kernel is not good enough ... Reassigning base to a register causes the ... generates the expected shifts and and masks for power of two divides. ...
    (Linux-Kernel)