Re: Need some simple bijective mappings

On 17 Tháng Sáu, 12:21, Maaartin <grajc...@xxxxxxxxx> wrote:
On Jun 17, 5:45 am, Tran Ngoc Duong <tranngocdu...@xxxxxxxxx> wrote:

On Jun 16, 7:59 pm, Maaartin <grajc...@xxxxxxxxx> wrote:
Right. Could you give me a reference in the literature?

I'm afraid I can't. Personally, I observed the group property myself
some time around 1994, when I was impressed by the "no S-boxes"
concept of the IDEA block cipher, and tried to "design" something like
it for 32-bit machines. The group property of 2*x*y + y + z came to me
first. When I found the isomorphism to the multiplicative group of odd
integers, generalization to (1<<m)*k*x*y + x + y followed easily. As
an undergraduate student without formal math-phys trainings, within my
(very limited) knowledge, I was not aware of such references in
literature. I'm not aware of that even now, too.

I ask only because I thought, there can be more information there. I
was impressed by IDEA, too, and I still wonder why it uses its
pseudomultiplication instead of something like 2*x*y+x+y, which can be
written as x + (2*x+1) * y, and executed using only 3 instructions on
x86 architectures using LEA.

And, on any architecture, if memory is not a very concern one may
precompute 2*x + 1 to save one instruction, as M. K. Shen has pointed
out.

I think Lai & Massey's decision for multiplication mod (2^n + 1),
rather than something like 2*x*y + x + y, was a right decision, after
balancing between implementation complication and mathematical
complexity (aka, level of "confusion").

Integer multiplication those days was very time-consuming in
comparison to addition and jumps, so from the implementation view the
two operations are, in essence, equally complicated. From the
mathematical view, on the other hand, multiplication mod (2^n +1) is
better since it is more "confusing". If my memory serves, Lai has
proved that the multiplication mod (2^16 + 1), unlike 2*x*y+x+y,
cannot be written as a polynomial over the ring Z(2^16). And maybe it
is superior to 2*x*y+x+y with respect to differential characteristics
(in relevant definitions of the "difference"), I think.
.