operations modulo a prime number +, + =, -, - =, =, ==,! =,>, <,> =, <=, *, * =, /, / =

Please describe these operations that I need to do through operator overloading, if not difficult with examples.

  • one
    Comparing the type of more / less in modular arithmetic is meaningless. - VladD
  • As I understood these actions are used in cryptography. for example, addition and subtraction is something like (a + b)% 2 ^ 32 - KappaPolice

1 answer 1

Regarding the description and meaning of operations, you better consult with any book on higher algebra. This part of the question lies outside the scope of our site. You can start, for example, with Wikipedia .

Regarding data representation: to avoid problems associated with overflow (and modulo-2 arithmetic associated with this) to the extent of word size, it is best to use a longer type for operations that is guaranteed to contain the result of multiplication. You can use the canonical representation of a number to store the value.

We get something like this (C ++):

template<unsigned int p> class Residue { typedef unsigned int working_type; typedef signed int diff_type; typedef unsigned long operation_type; static_assert(sizeof(operation_type) >= 2 * sizeof(working_type)); static_assert(p > 1); working_type value; static working_type reduce(operation_type value) { operation_type residue = value % p; assert(0 <= residue && residue < p); // ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ residue < p, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Ρ‚ΠΈΠΏΠΎΠ² бСзопасно return (working_type)residue; } static working_type reduce(diff_type value) { // Π½Π°ΠΌ Π½ΡƒΠΆΠ΅Π½ Π±ΠΎΠ»Π΅Π΅ ΡˆΠΈΡ€ΠΎΠΊΠΈΠΉ Ρ‚ΠΈΠΏ, Ρ‡Ρ‚ΠΎΠ±Ρ‹ слоТСниС с `p` Π±Ρ‹Π»ΠΎ бСзопасно operation_type residue = value % p; operation_type residue = (remainder < 0) ? (remainder + p) : remainder; assert(0 <= residue && residue < p); // ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ residue < p, ΠΏΡ€ΠΈΠ²Π΅Π΄Π΅Π½ΠΈΠ΅ Ρ‚ΠΈΠΏΠΎΠ² бСзопасно return (working_type)residue; } Residue(operation_type v) : value(reduce(v)) { } public: Residue(working_type v) : value(reduce((operation_type)v)) { } Residue(diff_type v) : value(reduce(v)) { } Residue<p> operator + (const Residue<p>& other) { // здСсь Π½Π΅ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ пСрСполнСния auto sum = (operation_type)value + (operation_type)other.value; return Residue<p>(sum); } // ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Π±ΠΎΠ»Π΅Π΅-ΠΌΠ΅Π½Π΅Π΅ Π°Π½Π°Π»ΠΎΠ³ΠΈΡ‡Π½Ρ‹ };

Watch out for possible overflow, it can spoil the result! Test for large p values.

Please note that if you need modulo 2^32 operations, you can simply use the usual arithmetic on uint32_t , the extra bits are discarded automatically. In addition to division, which will have to remember the Euclidean algorithm . (The sign type does not fit , the overflow on it has undefined behavior!) But this does not fit into your task, since the powers of two (the first one) are not prime numbers.