Skip to content

Division algorithms unification #811

@fjarri

Description

@fjarri

We have several very similar division algorithms implemented:

  • BoxedUint::div_rem_unchecked(), Uint::div_rem() - constant-time, requires same bits_precision() for both arguments
  • uint::boxed::div_rem_vartime_in_place() - variable-time, bits_precision() of arguments can be different, but the top limb of the divisor must be non-zero
  • Uint::div_rem_vartime() - variable-time, argument size can be different, the top limb of the divisor can be zero

It seems that some improvements are possible:

  • Merge constant-time and variable-time algorithms for boxed and stack integers. Need to check that it doesn't affect the performance for Uints
  • Possibly merge variable-time and constant-time versions?
  • Remove the same size restriction for constant-time algorithms. Should be possible, although care must be taken to keep the memory access pattern from revealing information about the arguments. This will help avoid reallocation in other places in crypto-bigint (look where resize() is used before division) and in other crates.
  • Remove the non-zero top limb restriction for div_rem_vartime_in_place() - since it's not the case for the Uint version
  • The remainder returned by the BoxedUint division should have the same bits_precision() as the divisor (mirroring the Uint behavior)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions