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 04:59:45 GMT

Jim Steuert wrote:

> 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.

What a mess. Jim has quoted out-of-order, making the discussion
incomprehensible.

> No it is a problem. It is the crux of the problem.
>
> I'm not surprised that you found pivots for this tiny example.

This was not some simplified example of my own construction. It
is the example Jim presented in the post to which I replied.

> But what if there is another "isolated" set of values
> say, t, which like 4, map only into t or u.
> Then "no" pivot will clear that entire column. Then you
> do not have upper-triangular at all.

I gave a general solution for the group mod 2^n, which I
previously showed to be isomorphic to the group Jim used in his
cipher. There's always a term for which the number of factors
of two is minimal, and that can serve as the pivot.

> You have not demonstated that Gaussian Elimination can
> be used with commutative rings when some values are without
> multiplicative inverses.

I demonstrated exactly what I claimed to demonstrate. Jim chose
the example, so that's the example I showed how to solve. The
pivot-choosing method is sufficient to show that Gaussian
elimination works to solve a layer of Jim's cipher.

> In fact, commutative rings needn't have any multiplicative
> inverses. Values can just multiplicatively cycle (which may be an
> advantage for this usage, as it may make Gaussian Elimination
> a combinational explosion) in disjoint sets of values (ideals).
> (but still come out of the cycles additively)
>
> And again, that is the crux of the original problem, which you have
> just deferred to another problem, without solving it.

Did someone promise to solve all Jim's problems for him?

Jim, if you want to investigate whether Gaussian elimination
works for all commutative rings, here's a simple way to look at
the problem: We can reduce the issue to the 2-row case, without
loss of generality. Consider two rows of the form:

     u, ...
     v, ...

where neither u nor v is zero. We can do the legal operations,
such as multiplying a row by a scaler other than zero, or adding
to a row any multiple of the other. Then we have to add a
multiple of one row to the other so that the sum begins with a
zero term.

Is there a commutative ring with a u and v such that we cannot
do the elimination? If yes, then Gaussian elimination can fail
- - these might be the only two rows remaining. If no, then it
always works -- we can take two rows at a time and eliminate
one, until there's only one non-zero term in the column.

> And again, that is the crux of the original problem, which you
> have just deferred to another problem, without solving it.
>
> I still suspect that it is a combinational problem.

Well then showing it should be easy. Just exhibit a commutative
ring and non-zero elements u and v, where we cannot do the legal
linear operations to eliminate one of them. 

-- 
--Bryan

Relevant Pages

  • Re: count on multiple conditions
    ... Jim, that makes sense, but I don't see this working well for my needs on this ... I have pivot tables set to retrieve the original information from my ... I want it to count how many neutrals I have for 8/1 and return ... I want to use a code that will search column b for a date: ...
    (microsoft.public.excel.worksheet.functions)
  • RE: Data Conversion (Weekly 2 Monthly) ???
    ... I don't know anything about pivot tables. ... What I need is a macro that will write formuals into cells after doing some ... Formula otherwise I might be averaging Jan and part of Feb into one monthly ... Anyhow not sure if anyone can help but I appreciate your input anyway Jim. ...
    (microsoft.public.excel.programming)
  • Re: Pivot Table not cooperating
    ... If there were supposed 3 of those lines it would show 300 in the available in each location for that item in the pivot table even though I only had 100 in each location for my spreadsheet. ... "Jim" wrote: ... "Debra Dalgleish" wrote: ... What's in the inventory table for that customer, and what would you like to see in the pivot table? ...
    (microsoft.public.excel.misc)
  • Re: Please help: Pivot Tables problem
    ... Jim May wrote: ... Is a Pivot Table even possible? ... "Dave Peterson" wrote: ... I need to be able to count the number of Yes and No responses to Q1, ...
    (microsoft.public.excel.misc)
  • Re: Rejected E-mails. Error Number: 0x800CCC78.
    ... Thanks Jim. ... The link you gave me mentioned about having multiple ISP's, which I don't, I just have the one ISP and one e-mail account. ... > Jim Pickering, MVP-Outlook Express ...
    (microsoft.public.windows.inetexplorer.ie6_outlookexpress)