-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I would need to established a reduced base of non commutative
operations. The operations should be grouped in 'rings' ( not
mathematical rings) in which no couple of operations shall comutate;
operations from different rings may commute, or even be identical.

The operations will manipulate integers of 8 to 128 bits.

I need to build rings of at least 3 operations, times 10 to 1000 rings.
10 in a week, and 1000 in 2 months.

Of course, no ring shall be totally included in any other one; otherwise
I d consider them as redundant. But rings containing more than 3
operators will be break down into smaller rings by a dedicated programm.

I d need an example of 3 to 5 rings, and then some theory on how to
build up to 1000.

All operations should be reversible in less than 10 more operation than
the initial one: if yor example operation A() needs 1s to be computed,
a-1() should not take more than 10s, so that I can reverse the result
of the whole ring before I die :) ( within 5 mn in fact )

Thank by advance.

I post that in both groups, because it is going to be implemented in C,
but I expect ppl from crypto groups to be more familiar with commutative
operations.

*** ( I have been said that the following example do not illustrate very
well my problem ... be aware that it could make you understand even
fewer than you already did ... if you ever understood anything up to
here ^^ ) ***

For example, I could accept modulo 17 operation in a ring, as long as my
program knows that the entry shall be less than 1000, so that it is
possible to retrieve the original number in reasonable time ( I still
have to find out how to know which boundary is the good one - storing a
key some where ? that is possible, but I guess there are better ways):
if n is the number I want to 'hide',
x=n%17
a=(n-x)/17
shall I store a somewhere ? or just keep a checksum of a or n ?

- --
DEMAINE Beno�t-Pierre http:/www.demaine.info/
\_o< apt-get remove ispell >o_/
There're 10 types of people: those who can count in binary and those who
can't
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFBjoKqGWSTLbOSw8IRAg4YAJ4nJaxDAkEiO2/t8c58/PPLZhSY+gCgtm1k
fltS/bG/d/pxjM10tEiXfoU=
=MM6s
-----END PGP SIGNATURE-----

In article <re6dnWxyevyvHhPcRVnyjQ@pipex.net>,
 DEMAINE Benoit-Pierre <nntp_pipex@demaine.info> wrote:

> I would need to established a reduced base of non commutative
> operations. The operations should be grouped in 'rings' ( not
> mathematical rings) in which no couple of operations shall comutate;
> operations from different rings may commute, or even be identical.

It seems to me that on the set of n-bit values, n>1, the
operations  OPj  defined as
   x  OPj  y =  (x xor j) + y  mod 2^n
are not commutative or associative, assuming 0 < j < 2^(n-1).
I don't know your exact definition of operations that "comutate",
maybe picking distinct OPj defined as above would fit.


   Fran�ois Grieu

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

|>I would need to established a reduced base of non commutative
|>operations. The operations should be grouped in 'rings' ( not
|>mathematical rings) in which no couple of operations shall comutate;
|>operations from different rings may commute, or even be identical.
|
|
| It seems to me that on the set of n-bit values, n>1, the
| operations  OPj  defined as
|    x  OPj  y =  (x xor j) + y  mod 2^n
| are not commutative or associative, assuming 0 < j < 2^(n-1).
| I don't know your exact definition of operations that "comutate",
| maybe picking distinct OPj defined as above would fit.
|
|
|    Fran�ois Grieu

Tu as un nom bien francais mon ami :)

about OPj : I did know that operation; the question is : is it possible
to implement ( when coming about writing the C code ) OPj in various way
so that one do not look like an other one ?

if no => OPj is then one non comutative operations amongst the 10 000 I
need.

if yes => how different can the implementations be ? how many
implementations can I write ?

How much does it cost in time to reverse the operation ? ( to recover X
given Y or the reverse )

The matter is not to find an operation which do not comutate with
itself, but operations that do not comutate with other ones.

What I need is a list of 1000 groups of at least 3 operations per group
such as operations inside a group do not commutate. BUT operations
inside a group SHALL NOT look familiar one to each other. ( I am sorry I
forgot this point in my first message )

The 1000 groups shall not be redundant, ie, the elements of one group
shall not be all at one time be also element of an other group. From
those 1000 groups of more than 3 operations each, I will deduce at least
10 000 sub groups of exactly 3 operations each, and all those sub groups
will be elements of the 1000 mother groups.

Does it sound more clear ?
- --
DEMAINE Beno�t-Pierre http:/www.demaine.info/
\_o< apt-get remove ispell >o_/
There're 10 types of people: those who can count in binary and those who
can't
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iD8DBQFBj2oRGWSTLbOSw8IRAhOxAKCyi13ZvNOfkTwbxXI6ywxrx+GrTwCfQlUM
0SoxoOrSMDp1jESx8k2+jm8=
=Yvr1
-----END PGP SIGNATURE-----