Re: Magic Flight: A New Public Key Algorithm stronger? than factoring

From: Bryan Olson (fakeaddress_at_nowhere.org)
Date: 07/08/03 

Date: Tue, 08 Jul 2003 21:06:55 GMT

Jim Steuert wrote:
>
> Francois Grieu wrote:
>
>> Knowing M and alices_public, by Gaussian elimination or some
>> faster method, it is easy to find one of the (possibly several)
>> alices_secret that match this equation.
>
> Gaussian elimination requires that values have
> multiplicative inverses. The basic operation is row-reduction - some
> constant times one row added to the other row makes zero.
>
> k*(4 x x x x . . . .)
> +(2 y y y y . . . .)
> => (0 z z z z . . . .)
>
> My problem is that k*4 is not "ever" equal to 2.
> If values all had inverses this would be easy.
> Just form k = -(4^-1)*2, and you're done.

No problem: use the row beginning with '2' as the pivot. For
mod 2^n arithmetic in general, use a term where the number of
factors of 2 is minimal.

> In the tabular commutative ring example
[...]
> If it could always be reordered so that
> the values with inverses are done first, but then the problem
> remains with the other rows... Re-ordering schemes could end
> up in circular loops.

Upper-triangular form is fine, and you never have to
un-re-order.

Note that re-ordering doesn't always work. For example, if we're
working mod-15, we might get to a column:

     3, ...
     5, ...
     9, ...
    10, ...

None of the terms divides all the others. Still not a problem:
we simply add the second row into the first to get a pivot with
an inverse. It might be an interesting exercise to prove or
disprove that for any (commutative) ring, there's always a
linear combination of rows that provides a pivot. 

-- 
--Bryan