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

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

Date: Wed, 09 Jul 2003 14:44:31 GMT

Jim Steuert wrote:
>
> Bryan Olson wrote
>> What a mess. Jim has quoted out-of-order, making the discussion
>> incomprehensible.
>
> Really?

Yes, really. My "What a mess..." followed your out-of-order
quote:

>> > Bryan Olson wrote:
>> >> 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.
>> >>
>> >> No problem: use the row beginning with '2' as the pivot.

That's out-of-order, and the "No problem..." doesn't make sense
in your re-ordering. It made perfect sense in my post where it
followed your example, and showed how to do Gaussian elimination
where you didn't think it could be done.

> What, now that you can't find a break,
> you are objecting to lossy commutative rings?

In this thread, you challenged Francois Grieu to find a one-
round break. That is now done. It's not yet clear whether it
works against multiple rounds.

> You didn't object before I rebutted Gaussian Elimination.
>
> I thought my objections to Gaussian Elimination were quite clear.
> And I didn't quote out of order. My objection to your alleged
> ring isomorphism, citing concrete examples of lossy commutative rings,
> came several hours before your's or Francois's post
> about Gaussian Elimination.

I'm not sure what you're talking about. Your objection to my
ring isomorphism was an incorrect claim that the rings were not
isomorphic.

> As I have clearly demonstrated, Gaussian Elimination does not
> apply to commutative rings in general when some values do not
> have inverses, and specifically when there are multiple
> sets (ideals) of multiplicative cycles.

We showed how to do Gaussian Elimination on the ring you chose,
where not all values have inverses. Hiding your head in the sand
isn't going to make it go away.

[...]
> There may well be an algorithm for breaking this. And the
> discussion has brought out some good issues.
>
> But you haven't demonstated a break for "lossy" commutative rings
> (with values without multiplicative inverses) in general.

You have not shown a single commutative ring in which Gaussian
elimination doesn't work.

> My paper will be about "lossy commutative ring" structures
> for "Magic Flight" usage. What types of commutative ring mixers,
> and structures of such rings, are immune to Gaussian Elimination,
> or other methods of solution? It will also address exponentials of
> commutative ring structures (from my post of Feb 25, 2001).

So far you have not even provided a proof that your "do_layers"
operation commutes, despite repeated requests. 

-- 
--Bryan

Relevant Pages

  • Re: principal ideals
    ... The question of which commutative rings have the property that every ... We will call these rings FGC rings. ... contained in only finitely many maximal ideals and every nonzero prime ...
    (sci.math.research)
  • Re: coprimality & gcd
    ... Some rings in particular? ... For more general commutative rings it is ... both c and b lie in. ... --- Calvin ...
    (sci.math)
  • Re: units, domains, irreducibles, primes, and all that
    ... Can the product of 2 nonunits be a unit? ... No for commutative rings; yes for noncommutative rings. ...
    (sci.math)
  • Difference between Groups, Rings, Integral Domains and Fields
    ... Was wondering if there are any pointers to the specific difference ... Rings are Abelian ... Integral Domains are commutative rings with identity and inverse (under ...
    (sci.math)
  • Re: coprimality & gcd
    ... Rings in general? ... this follows easily from the definition of the gcd ... For more general commutative rings it is ... Simpler: this proof works for both ideals and gcds: ...
    (sci.math)