Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
422
questions
0
votes
0
answers
164
views
Efficiently count the number of primitive roots in all moduli up to $n$
Let's define $f(n)$ as the number of primitive roots modulo $n$. That is, $f(n) = \begin{cases}\varphi(\varphi(n))&n=1,2,4,p^k,2p^k\\0&\text{otherwise}\end{cases}$. We want to efficiently ...
- 436
6
votes
0
answers
135
views
Newton type method for finite fields?
I have a polynomial $p(x)$ in $\mathbb{Z}/q\mathbb{Z}$ that is easy to compute for any $x$ but has an absurdly large degree $d > 2^{256}$. I know for a fact that it has a zero and I would like to ...
- 239
1
vote
0
answers
46
views
Condition on the minimality of Minkowski units
I am interested in to undrestand when the Minkowski units in real biquadratic number fields are minimal in the log unit lattices.
I have read some pieces of literature online which are investigating ...
- 11
0
votes
0
answers
255
views
Counting perfect powers using primes
Result
Let $n\in\mathbb{N}_{\geq1}$
$n$ is by definition a perfect power iff
$\,\ \exists m,k\in\mathbb{N}_{>1}:n=m^{\,k}$
Let $N(n)$ be the number of perfect powers $\leq n$
We define
$$\mathbb{...
- 53
0
votes
1
answer
102
views
Residues distribution modulo an interval
Given a number $n$ and an Interval $I = [ \; \lfloor n^{1/4} \rfloor, \lfloor n^{(1/3) \rfloor \;} ]$, can we say anything about the distribution of $\{ n \mod b \;\;| \; b \in I \}$?
In particular, ...
6
votes
1
answer
562
views
On a fast high precision numerical analysis C library
This is probably a $y=f(x)$ question, but I searched several times on the MathOverflow without success so I decided to explicitly ask for the help of other members: please feel free to ask me to ...
- 5,288
1
vote
0
answers
28
views
Does $2$ variable linear Diophantine equation in $NC$ imply $2$ dimensional shortest vector is in $NC$?
Consider the Linear Diophantine in known $a,b,c\in\mathbb Z$
$$ax+by=c.$$
Above can be solve by Extended Euclidean which is not in $NC$ as far as we know. It is clear if Extended Euclidean is in $NC$ ...
- 13.5k
0
votes
0
answers
144
views
On distribution of prime pairs coming from certain polynomials
Consider the polynomials
$$g(x)=(2x)^4+((2x)^2+1)^2$$
$$h(x)=(2x)^4+((2x)^2-1)^2.$$
If $k$ odd integers $x_1,\dots,x_k$ are uniformly randomly chosen in $(t,2t)$ and the polynomials are evaluated at ...
- 13.5k
13
votes
2
answers
587
views
How many players are needed so that two evenly matched teams can be picked?
We have a pool of $n$ players of a game, each player is assigned a "skill" which is an integer $1\leq s\leq 100$. We are now going to pick teams of $5$ players, where the team's skill is ...
- 315
0
votes
0
answers
316
views
Percent of rational coordinates that is a multiple of another point on the elliptic curve
Consider elliptic curves $E:= y^2=x^3+Ax+B $ (A, B are integers) which have points $P, Q$ with rational coordinates and satisfy $P=[n]Q, n>1$. Now consider the below problem:
Input: Rational ...
-2
votes
2
answers
144
views
Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$ [closed]
How to calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$, where $n$ and $m$ are positive numbers.
We guess that: the great common factor is $1$.
- 567
1
vote
0
answers
117
views
Quadratic equations over Gaussian integers
Given an equation $x^2\equiv(a+ib)\bmod(c+id)$ where $a,b,c,d\in\mathbb Z$ holds, how to test if the equation has solutions and how to find the solutions in polynomial in $\log(|abcd|)$ time if $c+id$ ...
- 13.5k
0
votes
0
answers
55
views
Using coppersmith for bounded solution of a short linear Diophantine problem
I have a $3$-variable linear Diophantine equation
$$ax+by+cz=r$$ where $a,b,c,r\in\mathbb Z$ are known and can be as large in magnitude as needed and I know the equation has a solution $x,y,z\in\...
- 13.5k
84
votes
2
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number n, the other player can only reply in two different ways: They can either ...
- 771
4
votes
4
answers
545
views
What or where is the series expansion of the function $\ln\bigl(\frac{\tan x}{x}-1\bigr)$ or $\ln(\tan x-x)$ around $x=0$?
It is known that
\begin{equation*}
\tan x=\sum_{k=1}^{\infty}\frac{2^{2k}\bigl(2^{2k}-1\bigr)}{(2k)!}|B_{2k}|x^{2k-1}, \quad |x|<\frac{\pi}{2}
\end{equation*}
and
\begin{equation*}
\ln\tan x=\ln x+\...
- 716
2
votes
0
answers
192
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.5k
1
vote
0
answers
110
views
Which real functions benefit from the Fundamental Theorem of Interval Analysis?
I'm reading Introduction to Interval Analysis, by Moore, Baker & Cloud and complementing it with Global Optimization using Interval Analysis, by Hansen & Walster.
Theorem 5.1 - Fundamental ...
5
votes
1
answer
293
views
Parity of number of solutions to Diophantine equations
By $MRDP$ resolution of Hilbert's tenth, we infer, counting number of solutions to Diophantine equations is undecidable.
Is parity of number of solutions to Diophantine equations undecidable?
- 13.5k
6
votes
0
answers
91
views
Equivalence of primes based on the partition of their Pisano periods
The period of Fibonacci numbers modulo $m$ is called Pisano period and its length is denoted as $\pi(m)$. Define the Pisano partition of $m$ as the set partition of the indices $\{0,1,\dotsc,\pi(m)-1\}...
- 29.1k
12
votes
1
answer
2k
views
Primality of a number of more than 50k digits
With modern tecnology is it possible to prove the primality of a number of more than 50k digits?
Obviously not a prime for which specific methods for testing primality are known like Mersenne primes.
- 147
1
vote
1
answer
92
views
Deduce kernel of isogeny from action on torsion points
I'm stuck with the following problem:
In Petit's work "Faster Algorithms for Isogeny Problems using Torsion Point Images", p. 8, he says that we can deduce $\ker \psi_{N_2}$ knowing the ...
- 63
3
votes
1
answer
148
views
What is meant by a meet-in-the-middle approach?
I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" (link) and he talks about meet-in-the-middle approach/strategy for solve some isogenies ...
- 63
5
votes
1
answer
417
views
Discrete log problem modified
Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log_g a < \log_g b$? (Here we ...
- 2,451
0
votes
0
answers
113
views
Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?
There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...
- 13.5k
2
votes
1
answer
210
views
Modular square roots problem which is $NP$ hard
It is well known extracting modular square roots modulo a composite number factors the modulus.
On other hand given $u,v>0$ and an integer $n$, deciding if there is a factor of $n$ in $[u,v]$ is $...
- 13.5k
1
vote
0
answers
62
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...
- 13.5k
4
votes
0
answers
142
views
What are the modularity conjectures for Artin motives?
Classically, singular cohomology is an important tool for studying topological spaces, in particular, complex varieties. In the mid-twentieth century it was realized that there are many analogues of ...
- 447
4
votes
2
answers
196
views
"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$
Given an integer $a$, I would like to build a table of entries $(p, \text{ord}_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}_p(...
- 43
3
votes
0
answers
249
views
Ask for a generating function or an explicit expression of a triangle of positive integers
Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...
- 716
3
votes
0
answers
112
views
Ways to tell from residues modulo prime factors if $z$ is below half point
Let $N=\prod_{k=0}^{k=m}{ p_k }$ be a square-free odd integer where $p_k$ is a prime. If we are given any integer $g$ such that $0<g<N$, it is very easy to tell if $g < \frac{N}{2}$ or not. ...
2
votes
0
answers
113
views
How to compute torsion subgroup $E[24]$ over $\overline{\mathbb{Q}}$
If I have an elliptic curve $E: y^2=x^3-15x+22$ over $\mathbb{Q}$ with CM from the imaginary quadratic field $\mathbb{Q}(\sqrt{-3})$ then how do I compute the $24$-torsion subgroup $E[24]$ over $\...
- 267
31
votes
8
answers
8k
views
Why is integer factoring hard while determining whether an integer is prime easy?
In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an ...
- 2,451
2
votes
0
answers
83
views
Integers solutions of products of truncated Riemann zeta functions
Let $n \in \mathbb{N}$ be a positive integer.
It is possible to prove that the equation $F_1(n)=m$ where $m \in \mathbb{Z}$ and
$$
F_1(n)=(1+2+\ldots+n)\cdot\left(\frac{1}{1}+\frac{1}{2}+\dots+\frac{1}...
- 1,303
0
votes
0
answers
45
views
Does this approximate linear Diophantine Equation have bounded number of solutions?
Consider the linear diophantine equation
$$\alpha u+\beta v =r+ \delta$$
where $\alpha,\beta,r\in\mathbb Q$ are known and their binary expansion has $O(k)$ bits to exactly represent them and $\delta\...
- 13.5k
15
votes
0
answers
318
views
Do primes of the form $4k+1$ ever lead the greatest prime factor race?
Analogous to Chebyshev's race between primes, I examined the race between primes in the greatest prime factors, GPF, of natural numbers. Similar to the regular prime race, in the GPF race, the ...
- 4,466
6
votes
2
answers
272
views
Does the $p$-adic regulator depend on Weierstrass model?
I am a little confused on the $p$-adic regulator on elliptic curves and what happens when you switch to different Weierstrass models. Restrict to ell. curves over $\mathbb Q$ for simplicity.
From my ...
- 195
13
votes
1
answer
544
views
Can we compute the first $n$ digits of $\pi$ in $F(n)$ time?
I've seen various fast algorithms for computing the first few, or directly the $n$-th, digits of $\pi$.
However, it seems to me that all these algorithms assume (see last sentence here) that there are ...
- 18.4k
0
votes
2
answers
235
views
Counting powerful integers. Lower bounds
Remark: The upper bounds are perhaps still more interesting; I may address them in another post.
PROBLEM: Find simple (numerically efficient) lower bounds for the number of powerful integers (...
- 4,532
8
votes
1
answer
349
views
Computational efficiency of character sums for counting finite field points on a curve
It is a well-known fact that one can compute the number of points on a curve over a finite field via character sums. For instance,
$$5+1+\sum_{x\in GF(5)}\varphi(x(1-x)(1-2x))$$
counts the number of ...
- 269
1
vote
1
answer
208
views
Robin's inequality for odd numbers
In this article (Theorem 1.2) there is a proof for Robin's inequality for odd numbers,
$\sigma(n)/n< e^{\gamma}\log(\log(n))$ where $\gamma$ is the Euler-Mascheroni constant and $\sigma(n)$ is the ...
4
votes
2
answers
238
views
Maximal entropy of integer partitions of $n$
Let $\operatorname{Part}(n)$ be the set of integer partitions of $n$.
A partition $p \in \operatorname{Part}(n)$ has $k$ summands and $d$ distinct summand $n_i$, with $d \leq k$ and $d$ frequencies $...
2
votes
0
answers
136
views
On GCD and lattice reduction
$LLL$ algorithm is vectorized version of Euclidean algorithm for $GCD$.
Even the $m=2$ case known to Lagrange and Gauss does not have an $NC$ algorithm for shortest vector.
If $GCD$ is in $NC$ and in ...
- 13.5k
4
votes
0
answers
107
views
Lattice reduction of basis with non-integer coefficients
Suppose I have an ordered basis $\{b_1, \dots, b_n\}$ of a lattice in $\mathbb{R}^n$, but I do not assume that $b_i \in \mathbb{Z}^n$ for all $1 \leq i \leq n$.
I would like to perform lattice ...
- 554
5
votes
1
answer
218
views
What are the solutions in numbers of $xyz \mid x^n + y^n + z^n$, $x,y,z$ globally coprime
What are globally coprime integers $x,y,z\in \mathbb Z^*$ such that $xyz$ divide $x^n + y^n + z^n$?
I have no other motivation for that problem but its inherent beauty and interest.
Note that it can ...
- 677
4
votes
0
answers
100
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in ...
- 13.5k
7
votes
1
answer
347
views
About the complexity of some operation involving integers
There are two integers: $A, B$. Given the below four allowed operations (and only them):
$A+1$, $A-1$, $\sqrt{A}$, $A^2$
Also, it is only allowed to take the square root of $A$ when this square root ...
- 71
0
votes
1
answer
119
views
Examples of real-time transcendental number and superlinear-time trancsendental number
Computation model is defined as Hartmanis and Stearns 4, it is well known that Liouvilles constant
$$C_L=\sum_{i=1}^{\infty} 10^{-i!}$$ is computable in real time or linear time 1, 5 especially ...
- 2,848
3
votes
0
answers
125
views
Recover cyclotomic integer with bounded coefficients from its known associate
Recall that two cyclotomic integers are called associated if their ratio is a unit in the corresponding ring of cyclotomic integers.
We will view cyclotomic integers as polynomials (of degree $<\...
- 29.1k
2
votes
0
answers
41
views
Reordering entries of integer symmetric matrix via linear combinations into a symmetric matrix with all its eigenvalues positive with det condition
Suppose we have a symmetric matrix $M\in\operatorname{Sym}{M}_{n}(\mathbb{Z})$ having some negative eigenvalues. Are there algorithms filling the entries of a (possibly) bigger symmetric matrix $M'\in\...
- 573
1
vote
0
answers
44
views
Algorithm to compute S-units in imaginary quadratic number field
What efficient algorithms are there to compute the $S$-units of a given imaginary quadratic field $K$, where $S$ is a finite set of non-archimedean primes?
Computing $S$-units are implemented in ...
- 557