Jump to content

Talk:Modular arithmetic

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 94.73.55.201 (talk) at 19:59, 30 January 2019 (→Source code correct?). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Template:Vital article

WikiProject iconMathematics B‑class Top‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
BThis article has been rated as B-class on Wikipedia's content assessment scale.
TopThis article has been rated as Top-priority on the project's priority scale.

Division?

What about division? In arithmetic mod 13, 1/2 is 7 since 7*2=1. In arithmetic mod 10, 1/2 is impossible. With prime modulo, only n/0 is impossible. — Preceding unsigned comment added by 2A01:119F:2E9:2F00:94F9:AF78:6BF0:839F (talk) 16:59, 31 August 2016 (UTC)[reply]

Dividing one element a by another element b is defined for all a and nonzero b only when the integers modulo n constitute a field. — Anita5192 (talk) 18:15, 31 August 2016 (UTC)[reply]
This is true. Nevertheless, this article lacks of section "Modular operations", in which modular operations (modular addition, modular multiplication, modular exponentiation, modular inverse, and modular division) are defined and described. For the moment this is only partially done, and distributed in several sections. The fact that modular inverses may be computed by either extended Euclidean algorithm or Fermat's little theorem is lacking, although fundamental. Also fundamental and lacking are: the use of modular arithmetic for efficient linear algebra over the rationals, and the difficult problem of discrete modular logarithm. In other words, this article needs a complete rewriting. I intended to do that, but I have not yet get the time for doing this. D.Lazard (talk) 21:36, 31 August 2016 (UTC)[reply]
If b has a multiplive inverse mod n (b has a multiplive inverse mod n if and only if gcd(b,n)=1), then we can define (a/b) in arithmetic mod n, the definition is a × (the multiplive inverse of b mod n), e.g. in arithmetic mod 35, 1/2 is 18 and 1/3 is 12, but 1/5 is undefined, since 5 has no multiplive inverse mod 35. — Preceding unsigned comment added by 49.219.177.6 (talk) 11:03, 27 July 2018 (UTC)[reply]

Source code correct?

The source code in the page (reproduced below) allows values for m as large as 2^63 - 1, while simpler source codes usually require that m < 2^32, because of intermediate squaring operations involved that would overflow a 64-bits integer.

But...

I doubt that this source code is correct: 

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d > m) d -= m;
       a <<= 1;
   }
   return d;
}

Indeed, I translated it in C# as follows and I don't get correct results (tested against the BigInteger.ModPow(A, B, M) function provided in the .Net version 4): 

public static UInt64 ModPow(UInt64 A, UInt64 B, UInt64 M)
{
    const UInt64 Mask = (UInt64)1 << 63; // 0x8000000000000000UL

    UInt64 D = 0;
    UInt64 MP2 = M >> 1;

    A %= M;
    B %= M;

    for (int i = 0; i < 64; i++)
    {
        D = (D > MP2) ? (D << 1) - M : D << 1;

        if ((A & Mask) != 0)
            D += B;

        if (D > M)
            D -= M;

        A <<= 1;
    }

    return D;
}

Can someone help? Otherwise the source code above should be removed from the page.

The source code below requires that M < 2^32, but at least it gives the correct result (tested against the BigInteger.ModPow(A, B, M) function): 

public static UInt64 ModPow(UInt64 A, UInt64 B, UInt32 M)
{
    UInt64 R = 1;
    UInt64 C = A % M;

    while (B != 0)
    {
        UInt64 Bit = B & (UInt64)1;
        B >>= 1;

        if (Bit == 1)
        {
            R *= C;
            R %= M;
        }

        C *= C;
        C %= M;
    }

    return R;
}

Thanks. — Preceding unsigned comment added by Jp.basuyaux (talk • contribs) 12:26, 28 December 2016 (UTC)[reply]

I tested it out on C, and it appears to work for me.

This code here might be easier to understand, and the loop won't always run 64 iterations. It works for any uint64_t. 

uint64_t mul_mod2(uint64_t a, uint64_t b, uint64_t m)
{
        uint64_t sum = 0;
        if (a >= m) a %= m;
        if (b >= m) b %= m;
        while (b) {
                if (b & 1) {
                        if (sum < m - a) // if (sum + a) < m
                                sum += a;
                        else
                                sum += a - m;
                }
                if (a < m - a) // if (a + a) < m
                        a += a;
                else    
                        a += a - m;
                b >>= 1;
        }
        return sum;
}

- Anonymous  — Preceding unsigned comment added by 69.147.212.194 (talk) 14:34, 21 September 2017 (UTC)[reply]

Indeed it doesn't work. Copying and pasting both Anononymous' code and Wikipedia's article both fail with integers close to ULLONG_MAX of clmits, in particular (ULLONG_MAX-1)^2 modulo (ULLONG_MAX-82). It is better to just use the property: (a*b) mod m = (a-m)*(b-m) mod m.

Example implementations

The code in this section pertains to the binary modulus operator and not really congruence classes; so it should probably be moved to the Modulo operation page. 199.34.4.20 (talk) 17:51, 17 April 2018 (UTC)[reply]

Hello fellow Wikipedians,

I have just modified 2 external links on Modular arithmetic. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 10:36, 3 February 2018 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Talk:Modular_arithmetic&oldid=880995309"