Re: More about --- Formulae for Latin squares of size 2^n
From: Terry Ritter (ritter_at_ciphersbyritter.com)
Date: 12/07/03
- Next message: r.e.s.: "Re: Formulae for Latin squares of size 2^n"
- Previous message: Tom St Denis: "Re: Good enough for crypto?"
- In reply to: Cyber Vagrant: "More about --- Formulae for Latin squares of size 2^n"
- Next in thread: Cyber Vagrant: "Re: More about --- Formulae for Latin squares of size 2^n"
- Reply: Cyber Vagrant: "Re: More about --- Formulae for Latin squares of size 2^n"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 6 Dec 2003 16:13:21 -0800
cybervagrant@yahoo.com (Cyber Vagrant) wrote in message news:<9f8a576b.0312060847.7d89c836@posting.google.com>...
> Pardon me for starting a new thread but my news reader is having a
> problem continuing the original one.
>
> > Another option is to support a keyable feedback
> > polynomial for each, so that very little about each
> > internal RNG is constant and known by the opponent
> > without having to work for it. The user can develop
> > primitive feedback polys off-line, which become part
> > of the structure of the system. I have done this, but
> > operation was slow on a 25MHz 386. Any particular set
> > of polys can be transported in the same way the keys
> > are transported.
>
> I been wanting to do that for a while now, but I need to get a copy of
> 'The Art of Computer Programming' since nobody seems to be giving away
> algorithms to factor out primitives from irreducibles :)
>From my Crypto Glossary, under Primitive Polynomial:
"One way to find a primitive polynomial is to select an
appropriate Mersenne prime degree and find an irreducible
using Algorithm A of Ben Or:
1. Generate a monic random polynomial gx of degree n over GF(q);
2. ux := x;
3. for k := 1 to (n DIV 2) do
4. ux := ux^q mod gx;
5. if GCD(gx, ux-x) <> 1 then go to 1 fi;
6. od
Ben-Or, M. 1981. Probabilistic algorithms in finite fields.
Proceedings of the 22nd IEEE Foundations of Computer Science
Symposium. 394-398.
"The result is a certified irreducible. GF(q) represents the
Galois Field to the prime base q; for mod 2 polynomials,
q is 2. These computations require mod 2 polynomial arithmetic
operations for polynomials of large degree; "ux**q" is a
polynomial squared, and "mod gx" is a polynomial division.
A "monic" polynomial has a leading coefficient of 1; this is
a natural consequence of mod 2 polynomials of any degree. The
first step assigns the polynomial "x" to the variable ux; the
polynomial "x" is x**1, otherwise known as "10".
"To get primitives of non-Mersenne prime degree n, we certify
irreducibles P of degree n. To do this, we must factor the
value 2**n - 1 (which can be a difficult problem, in general).
Then, for each factor d of 2**n - 1 we create the polynomial
T(d) which is xd + 1; this is a polynomial with just two bits
set: bit d and bit 0. If P evenly divides T(d) for some divisor
d, P cannot be primitive. So if P does not divide any T(d)
for all distinct divisors d of 2**n - 1, P is primitive."
Personally, I have a bias toward using polys of Mersenne
prime degree, or powers of 2.
> Hmm,
> dynamically keyed taps on the generators. I can add that into my
> dynamically combined trio scheme. BTW my minimal machine for anything
> these days is a 100MHz Pentium, I can get them at aution for $50 a
> palet load. It must have been a while ago if you used a 386 for
> testing :)
Circa 1990.
> The PRNGs I coded were rather picky about the prim-poly used. It
> seems that some performed less well than others with out any apparent
> reason. May be using more than three taps would smooth out these
> differences between different polys. I saw that you used nine taps in
> Cloak-II.
One of the issues is raw size. Once one gets beyond,
say, 500 elements, I would expect trinomials to be OK.
If we support feedback 9-nomials, then the number of
possible feedback structures is of keyable size.
> > > Even in sight of that, the thought, of creating code able to create an
> > > arbitrary number of random large keyed OLSs on demand, seemed
> > > overwhelming, UNTIL, I noticed that each, of the 144 possible
> > > permutations of the standard non-linear latin square of order 4, is
> > > orthogonal to exactly 24 of the other permutations and futhermore that
> > > this group of 24 permutations is orthogonal to exact five other
> > > permutations outside of it.
> > >
> > > That is to say, the 144 possible permutations can be divided into six
> > > specific groups each of which is orthogonal to six and only six other
> > > permutations outside of the group. This information can be kept in a
> > > 6x24 array. This fact means that it is possible to write code capable
> > > of building any number of random orthogonal pairs on demand with only
> > > a modest amount of work.
> >
> > I'm not sure I understand this fully. I wonder how
> > that differs from what I wrote in my 1998 oLs article:
> >
> > http://www.ciphersbyritter.com/ARTS/NONLBBM.HTM
>
> Evidently, I was wrong there. Drat, that was the fist time ever.
>
> I enumerated by hand, because coding something to do it would have
> taken even longer,
That seems incredible to me. What a job!
Yes, coding often takes longer than the same thing
might by hand, but when the coding is done, the
results are exact, and can be repeated in a slightly
different way if a new idea surfaces.
Still, it would have been impossible for any hand
approach to have exposed the single base square in
the first place.
>each of the 144 possible permutations of the
> standard 4x4 square. I then checked each one to find the others it
> was orthogonal to. I found that each one is orthogonal to 48 others,
> I erred before stating 24,
There are 48 ordered pairs with a given Ls in the
first position, and some Ls in the second. So,
independent of position, each "pair" is represented
twice. But then position becomes another random
variable, because position does matter.
>and that the group of 48 that any one
> permutation is orthogonal to is also orthogonal to 23 others.
> Futhermore there exist exactly six groups of 48 permutations >>>that
> can be predefined<<< that one of which will be orthogonal to any
> arbitrary permutation of the standard 4x4 square.
I'm not sure I understand this: We have 144 permuted
squares. So if we have 6 distinct groups of equal size,
there must be 24 squares in each, right?
But we know that any particular square has 48 orthogonal
partners, not 24. So how does that work?
> Now correctly I hope, this means that all one has to is store in a
> table(144x2) a permutation identifier and a identifier for the group
> it is orthogonal to, and in another table(6x48) a group identifier and
> a list of permutations each group is orthogonal to. With this,
> creating any number or orthogonal pairs is trival: Pick a random
> number between 1 and 144 and another between 1 and 48. Voila, a
> random pair without testing.
Assuming such structure exists, we could construct
144 x 48 = 2112 orthogonal pairs, but we know there
actually are 6912. Something seems wrong here. We
need to cover them all, equally.
--- Terry Ritter 1MB Crypto Glossary http://www.ciphersbyritter.com/GLOSSARY.HTM
- Next message: r.e.s.: "Re: Formulae for Latin squares of size 2^n"
- Previous message: Tom St Denis: "Re: Good enough for crypto?"
- In reply to: Cyber Vagrant: "More about --- Formulae for Latin squares of size 2^n"
- Next in thread: Cyber Vagrant: "Re: More about --- Formulae for Latin squares of size 2^n"
- Reply: Cyber Vagrant: "Re: More about --- Formulae for Latin squares of size 2^n"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
