0
votes
0answers
21 views

Modulo and power calculation [on hold]

Let $A{^-}{^n}$ mod X = ($A{^-}{^1}$ mod X )${^n}$ mod X for $n>0$ Now we want to compute $A^B$ mod X fro given A,B and X provided A and B are coprime. Note : $A{^−}{^1}$ mod X refers to the ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
1
vote
1answer
51 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
-2
votes
2answers
144 views

How to find sum of 4th power of n numbers mod m [closed]

How can i calculate $1^{4} + 2^{4} + 3^{4} + 4^{4} .....+n^{4} \pmod m$ where $1 \le m \le 10^5$ and $1\le n \le 10^{20}$. I can't use the formula here because it will Overflow the limit of long long ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
2answers
113 views

Modulus of large powers

Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$. We need to find if $X \mid ...
-2
votes
1answer
263 views

Modulo of a large sequence of $1$s

Given two numbers $N$ and $M$, we need to find the remainder when $111 \cdots1$ ($N$ times) is divided by $M$. Here $N$ can go up to $10^{16}$ and $M$ up to $10^9$. How to solve this problem? ...
1
vote
1answer
41 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
0
votes
1answer
57 views

AP term multiple of prime number

I am having this equation : (a+(n-1)d)%p=0 Here a and d can go upto 10^18 and p is prime number upto 10^9 . How to find the least value of n here? Example : If ...
1
vote
1answer
29 views

Find a polynomial mod $n$ injective on a given set

This question is inspired by this challenge on CodeGolf.SE, in which the goal is to create a hash function with specified collisions. I thought a polynomial over the integers mod $n$ might be a nice ...
0
votes
0answers
52 views

What is an algebraic expression over a field structure?

I am working on a problem, and I am not understanding the language very well. Here is the setup of the problem: Consider the set $\{ 0, 1, 2 \}$ with the operations addition $(+)$ modulo $3$ and ...
0
votes
1answer
56 views

finding a unique integer using mod

Consider two different prime numbers $x$ and $y$. Show that the following is true: For every pair of numbers $m$ and $n$ so that $0\le m<x$ and $0\le n< y$, there is a unique integer $q$, where ...
1
vote
2answers
32 views

Computing modular inverses for a sequence of numbers

I have a prime $p$ and an integer $L$ such that $p \gg L \gg 1$, and I need to compute modular inverses of numbers $1, 2, \ldots, L$ (modulo $p$). Obviously I could apply the extended gcd algorithm to ...
0
votes
1answer
88 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
1
vote
1answer
69 views

Probabilistic time algorithm for finding the solution for quadratic congruences (case when p is prime)

I was trying to solve the following equation: $$y = x^2 \bmod p$$ where $p$ is prime. I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I ...
1
vote
1answer
226 views

Modulo over rational numbers?

Consider two irreducible fractions: $r_1 = \frac{p_1}{q_1}$ $r_2 = \frac{p_2}{q_2}$ with $r_1 \ge 0$ and $r_2 \ge 0$. How the modulo $\%$ is defined over rational numbers (I think that is $r_3$ ...
0
votes
1answer
21 views

Diffie hellman and the discrete algorithm problem

Suppose Alice and Bob are exchanging keys using Diffie-Hellman Key-Exchange Algorithm. a - Alice secret key g - generator p - prime x - the public key passed from Alice to Bob. Eve is listening to ...
1
vote
2answers
46 views

$( x \cdot y ) \mod 37 = 1$

I am doing a paper for my security class. I have this equation which I'm trying to understand $$( x \cdot y ) \mod 37 = 1 $$ e.g. if $x = 8$ and $y = ?$ ; which ...
4
votes
1answer
237 views

Square root algorithm in modulo $n = pq$

I've been stuck in this problem quite a bit. I have to find an efficient algorithm wich, given: $$ p = 4k+3\\ q = 4m+3\\ p,q \hspace{2mm} \text{odd primes}\\ a\in \mathbb{N} $$ verifies if there ...
1
vote
1answer
32 views

How to find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x<p

For a given prime $p$, how do I find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x < p? The problem is that trying thoroughly every $x < p$ is too inefficient. I ...
1
vote
1answer
100 views

Quick algorithm to compute the order mod m for an element from quadratic field?

For $a+b\sqrt{q}$,where a, b, q are integers and q is square-free, what's the quick algorithm to find the minimal integer n that $(a+b\sqrt{q})^n=1\pmod{m}$? P.S. ...
1
vote
0answers
70 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
2
votes
1answer
228 views

How to prove algorithm for solving a square congruence when p ≡ 5 (mod 8)

I'm having trouble understanding why this algorithm works and where it comes from: "Suppose p ≡ 5 (mod 8) is a prime and y is a square (mod p); that is, for some $ x, x^2 ≡ y\ (mod\ p)$. This can be ...
1
vote
1answer
259 views

Solutions of non-linear congruence equation

I am trying to find the number of solution to $$ x^a(\mod b) =c:0\leq x\leq l$$ where $b\leq50$ but $a$ and $l$ can be large. My approach is to iterate through each value of $x$ from $0$ till ...
1
vote
1answer
353 views

Encryption using modular addition and a key

Problem i'm facing says: The value representing each row is encrypted using modular addition with a modulus of 32 and a key of 27. I sort of figured out what ...
1
vote
0answers
53 views

How can I solve this using BIT?

I found a nice math problem, but I still can't solve it, I tried to find one solution using google and found that it can be solve using the Binary Indexed Tree data structure, but the solution is not ...
1
vote
1answer
1k views

HINT for summing digits of a large power

I recently started working through the Project Euler challenges, but I've got stuck on #16 (http://projecteuler.net/problem=16) $2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = ...
2
votes
1answer
70 views

Modulo in e-voting paper is wrong?

I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf). I have chosen as parameters the following: the ...
2
votes
1answer
46 views

Efficient modular exponentation of powers

Is there any way to efficiently compute $(((\mathrm{base}^{M_1})^{M_2})^{M_3} \dots )^{M_n}$ modulo $P$, where $P$ is prime? One way is to repeatedly do modular exponentiation for each of the powers. ...
2
votes
1answer
76 views

Solve the special congreuences equation?

the following congruencies $\begin{matrix} x_1\equiv1~(\mod m_1)\\ x_2\equiv1~(\mod m_2)\\ \vdots\\ x_n\equiv1~(\mod m_n)\\ \end{matrix}$ where $m_i, m_j(i\neq j)$ are pairwise coprime. Now, I known ...
3
votes
2answers
493 views

What does it mean to “have a multiplicative inverse of modulo 10!”?

Here's the question: What's the smallest integer > 1 that has a multiplicative inverse modulo 10! (that is, 10 factorial)? What does that mean? I understand that: We say that x is the ...
3
votes
2answers
379 views

Linear equation system in modular aritmetic

Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe. $$4x_1 - ...
0
votes
1answer
321 views

Running time of Modular Exponentiation

I am trying to understand why the modular exponentiation algorithm has a running time of about $\log(n)$ where $n$ is the exponent. Here is the algorithm: ...
3
votes
1answer
87 views

Is there a way to find the value of $1^n+ 2^n +\cdots + m^n$ modulo $x$?

I am writing a program in which I want to make changes to make it more efficient. What the program does is it takes three inputs $m$, $n$ and $x$ and I have to find the value of the following ...
2
votes
1answer
491 views

Computational Complexity of Modular Exponentiation

The following was posted from a lecture: "($a^n \bmod N$) has a runtime complexity of $\mathcal{O}(n*|a|*|N|)$ using the brute force method. $Z_1 = a \bmod N$ $Z_2 = (aZ_1) \bmod N$ $Z_3 = (aZ_2) ...
1
vote
1answer
423 views

Modular Multiplicative Inverse & Modular Exponentiation Equation

I was solving a problem containing that equation. $$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$ Given: $1 \le a \le 2,000,000,000$ $0 \le n \le 2,000,000,000$ $2 \le m \le 2,000,000,000$ $a$ and $m$ ...
0
votes
2answers
227 views

Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
1
vote
1answer
755 views

Solving modular inequalities/constraint solving

A few of my current programming problems boil down to solving inequalities over modular domains and possibility could benifit from knowledge of efficient maths/algorithms rather than brute force ...
2
votes
1answer
1k views

Quick algorithm for computing orders mod n?

Is there a fast way to compute the order of $a \pmod n$ without computing potentially all the powers of $a$ up to $n-1$? For example, in computing the order of $87 \pmod {101}$, the naïve way could ...
2
votes
2answers
807 views

Schönhage-Strassen multiplication

I am trying to implement the Schönhage-Strassen algorithm (SSA) for multiplying large integers, but it only gives the right result if all $\delta_j$ are zero. I'll explain what I mean by this: SSA ...
6
votes
4answers
1k views

calculating n choose k mod one million

I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula $$ {n\choose k} = {n\choose k-1} \frac{n-k+1}{k} $$ so I don't have to calculate huge ...
0
votes
1answer
885 views

solving modulo equation

How to solve this $$x^a \equiv b \pmod n$$ I need to be able to find $x$, given $b$. $a$ is always $23407534262244700$ and $n$ is $465992738619896000$. Someone mentioned I can use Fermat and ...
1
vote
0answers
94 views

Computing a generating set of the kernel of a module

Given a generating set of a $\mathbb{Z}$-module $M \subseteq {\mathbb{Z}_k}^n$, is there a known algorithm to compute a generating set of $\{u \in {\mathbb{Z}_k}^n \, : \, \forall v \in M \quad v ...
0
votes
0answers
86 views

Why this modulo p transformation works?

I came across some transformation modulo p, while solving MIT algorithms course assignment, that I couldn't get. We have n bits long binary number A. I have a value of x1 mod p (p - random prime ...
2
votes
1answer
826 views

Fast algorithm for modular division (residue)

I'm looking for a fast algorithm to perform division of large numbers (by hand). Traditional long division just isn't fast enough for my needs. In most of these cases, I'm only looking for the ...