Skip to content

bug: emulated Exp and ModExp take exponents as field elements #1148

Open
@ivokub

Description

@ivokub

The emulated methods Exp and ModExp take exponents as the same field elements as base, but in practice they do not belong to the field.

This is particularly case for the Exp method where when we obtain the exponent through a computation

l := f.Mul(b, c)
res := f.Exp(a, l)

then l can be either l or l+p (as the value is provided from hint). In this case, the result could be incorrect.

My proposal:

  • either omit Exp method as the method signature is just incorrect. Or it should take as an input frontend.Variable (or bits directly?) and we add documentation that we represent this as an integer.
  • add documentation for ModExp method which explains that exponent is not from the same field. Or we should already take bits as an input.

In both of the cases, actually it could be beneficial when we take directly bits as an input as this would allow to optimize the number of loops when computing the modular exponentiation (the number of loops is the length of the bits slice).

Metadata

Metadata

Assignees

Labels

bugSomething isn't workingconsolidatestrengthen an existing featuredoc

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions