Large number modulus calculation

post by yfmao on Feb 12, 2021

I am asking about how to implement a large number modulus in TEAL code.

Here I have a number of 256 bits waiting for mod computation. But, TEAL only support uint64, meaning that this size of 256-bit integer is not supported. My primitive idea is to store the number into 4 chunks, where each chunk stores 64 bits. Then, the mod action will be executed by reading & updating the values in the four chunks repeatedly.

Theoretically my large number modulus is feasible, but in practice this might be time costly, and the size of TEAL code will be very large. Is there any easier way to do that task?

post by fabrice on Feb 12, 2021

Are you trying to compute x mod y, with both x and y of 256-bit?

Is there any structure in x or y?

For example, is y of the form 2^256 - small number, this can simplify computation.

Instead of doing a modulus reduction, can you just verify that x mod y = z, by having the caller of the smart contract provide k such that x = z + ky (such computation is easier).

If you do not mind me asking, what is the use case for such computation?

post by yfmao on Feb 12, 2021

@fabrice Thanks for your reply.

I think I am computing x mod y where both x and y are 256 bits. The difficulty of this problem is how to store the two large numbers x and y into the smart contract efficiently. It seems that smart contract does not support number of that size. Do you have any ideas on how to store the number larger than 64 bits?

post by fabrice on Feb 12, 2021

You can store it either as 4 uint64 or just as bytes.

In both cases, the modulo operation will be expensive, and I am not sure you can actually do it within the cost limits (but I may be wrong).

However, you may be able to make many optimizations depending on the use case and on what can be provided from outside, e.g., as argument.

Hence the above questions.

If you do not want to make the use case public, you can DM me if you prefer.