0
votes
0answers
47 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
51 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
28 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
62 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
46 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
100 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
18 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
42 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
162 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
30 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
69 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
65 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
176 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
235 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
214 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
50 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
495 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
68 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
45 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
74 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
415 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
306 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
238 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: ...
2
votes
1answer
79 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
372 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
362 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
205 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
660 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
723 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
903 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
769 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
93 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
82 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
785 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 ...