All Questions
Tagged with prime-factorization modular-arithmetic
27
questions with no upvoted or accepted answers
7
votes
0
answers
174
views
I found a way to calculate Quadratic min mod $N$, but why does it work?
I am trying to factor $N$ using Dixon's factorization method, so I am looking at the equation:
$$a^2\equiv b(\mod{N})$$
If I am able to find $b$ that is a perfect square, I will be able to factor $N$...
- 1,450
5
votes
1
answer
224
views
An approximation for $1\leq n\leq N$ of the number of solutions of $2^{\pi(n)}\equiv 1\text{ mod }n$, where $\pi(x)$ is the prime-counting function
We denote the prime-counting function with $\pi(x)$ and we consider integer solutions $n\geq 1$ of the congruence $$2^{\pi(n)}\equiv 1\text{ mod }n.\tag{1}$$
Then the sequence of solutions starts as $$...
user243301
4
votes
0
answers
99
views
Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$
As a continuation of this question relating the Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is composite and this other one on the divisibility of numbers in intervals ...
- 1,190
4
votes
0
answers
243
views
Proper divisors of $P(x)$ congruent to 1 modulo $x$
Let $P(x) $ be a polynomial of degree $n\ge 4$ with integer coefficients and constant term equal to $1$. I am interested in Polynomials $P(x) $ such that for a fixed positive integer $b$, there are ...
- 234
2
votes
1
answer
106
views
Integer Factor Congruence
Given an integer $N$, with unknown prime factors $f_1$, $f_2$ ... $f_n$, and given unique integers $k_1$, $k_2$ ... $k_n$, with $\sqrt{N} \geq k_i>2$ for all $i$ such that
$$f_1 \equiv 1\pmod {k_1}$...
- 365
2
votes
0
answers
505
views
Using factorization to solve modulo arithmetic involving big numbers.
In one of my classes, the following approach was shown to solve modulo operations involving huge numbers:
Problem to solve:
49 10 mod 187.
Approach taken:
Prime factorize $187$. It's factors are ...
- 141
2
votes
1
answer
78
views
Large prime divisors in small intervals
For my thesis I would like to find integers (lying in a certain moduloclass) in small intervals which have large prime divisors. And for some reason I decided that I want all bounds appearing in my ...
- 989
2
votes
0
answers
433
views
Question regarding the prime factors of $2^{35} - 1$
Question regarding the prime factors of $2^{35} - 1$
I just wanted to make a few things clear;
1) It is true to state that this cannot be a Mersenne prime (A number of the form $2^r - 1$ where if ...
- 311
1
vote
0
answers
84
views
Find the remainder when the $2006! + \dfrac{4012!}{2006!}$ is divided by $4013$
$$2006!+\frac{4012!}{2006!}=x \pmod{4013}$$
Answer: $x=1553.$
Solution: $$2006!+4012!/2006!=x\pmod{4013}$$
$$(2006!)^2 -2006!x+4012!=0\pmod{4013} (*)$$
$$4\cdot (2006!)^2-4\cdot 2006!x+4\cdot 4012!=...
- 11
1
vote
0
answers
122
views
Sum of members from multiplicative group of prime order $k$ modulo prime $P$? $c$ in: $\sum_{n=1}^{k} (g^n \bmod P) = c \cdot P$ ($g$ prime order $k$)
Let $P$ be a prime ($>2$) and $g$ a value between $2$ and $P-2$.
Let $M$ be the set of numbers which can be generated with $g$:
$$M = \{g^n\bmod P, \text{ with } 0 < n <P \}$$
If $g$ is a ...
- 77
1
vote
0
answers
39
views
Baby steps to factorization of a large composite number via modular arithmetic
Given a huge composite number with unknown prime factors and a much smaller prime modulus P, is there a way (short of the Herculean task of factorization) to identify the residue classes mod(P) of the ...
- 111
1
vote
0
answers
299
views
Pohlig-Hellman algorithm
I'm trying to use the Pohlig-Hellman algorithm to solve for $x$ where $15^x=131(\bmod 337)$. This is what I have so far:
prime factors of p-1: $336=2^4*3*7$
$q=2: x=2^0*x_0+2^1*x_1+2^2*x_2+2^3*x_3$
...
- 297
1
vote
0
answers
198
views
Proving a number is a factor of a in (a mod N)
Suppose you had a very large composite number, which is the product of a couple large primes. Let's call this $a = c_1c_2c_3c_4$ where $c_1,c_2,c_3$ and $c_4$ are all primes.
If you calculated $d = ...
- 111
1
vote
0
answers
33
views
What is the best way to factor a value if modulo is used
If i have the following values
$(1) m\prime=(r^e.m) \% n$
$(2) s\prime=(r.m^d) \% n$
If i have access to the value of $m$,$d$, $m^d$,$m\prime$,$s\prime$,$n$,$p=11$,$q=19$, $\phi=(p-1)(q-1)=180,$ ...
- 121
1
vote
0
answers
100
views
can i compute the inverse mod m by inverting the prime factors?
I have $a \in \mathbb{Z}/\mathbb{mZ}$ and $a = p_1 * p_2$ in $\mathbb{Z}$ ($p_i$ are primes).
Furthermore, it holds $gcd(a,m) = 1$, so there exists an $a^{-1} \in \mathbb{Z/mZ}$.
Would be ok to ...
- 111