Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
5
votes
1
answer
461
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 ...
- 10.4k
0
votes
0
answers
122
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.9k
1
vote
0
answers
70
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.9k
4
votes
0
answers
206
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 ...
- 815
13
votes
1
answer
609
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 ...
- 63.9k
3
votes
0
answers
116
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. ...
- 190
5
votes
2
answers
510
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(...
- 121
5
votes
4
answers
791
views
Proving a least prime factor
Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $...
- 9,114
2
votes
0
answers
132
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 $\...
- 63.9k
6
votes
2
answers
308
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 ...
- 8,945
1
vote
2
answers
271
views
Ask for a reference or a proof of an identity involving a finite sum and the Bernoulli numbers
Let $B_{n}$ for $n\ge0$ denote the Bernoulli number generated by
\begin{equation*}
\frac{z}{\textrm{e}^z-1}=\sum_{n=0}^\infty B_n\frac{z^n}{n!}=1-\frac{z}2+\sum_{n=1}^\infty B_{2n}\frac{z^{2n}}{(2n)!},...
- 1,091
2
votes
2
answers
283
views
Ask for a proof of an identity involving the product of two Bernoulli numbers
It is well known that the Bernoulli numbers $B_{k}$ for $k\in\{0,1,2,\dotsc\}$ can be generated by
\begin{equation*}
\frac{z}{\textrm{e}^z-1}=\sum_{k=0}^\infty B_k\frac{z^k}{k!}=1-\frac{z}2+\sum_{k=1}^...
- 1,091
2
votes
0
answers
93
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}...
- 6,367
1
vote
1
answer
323
views
Number of biquadrates mod n
Is there an explicit formula for the number of fourth powers mod n?
Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...
- 2,075
15
votes
0
answers
365
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 ...
- 12.9k
0
votes
2
answers
288
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 (...
- 105k
8
votes
1
answer
390
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 ...
- 28.2k
1
vote
1
answer
282
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 ...
- 25.7k
4
votes
2
answers
295
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 $...
- 4,529
2
votes
0
answers
201
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.9k
4
votes
0
answers
137
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
234
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 ...
CommunityBot
- 1
4
votes
0
answers
104
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 ...
0
votes
1
answer
250
views
If the coefficient of the polynomial positive
I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...
- 50.8k
7
votes
1
answer
352
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 ...
- 6,367
0
votes
1
answer
125
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 ...
- 3,094
3
votes
0
answers
135
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 $<\...
- 34.3k
2
votes
0
answers
45
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\...
- 3,691
1
vote
0
answers
50
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 ...
- 577
7
votes
1
answer
623
views
Algorithm for computing whether a cubic field is monogenic?
I am interested in existing algorithms to compute whether a given non-cyclic, non-pure cubic extension $K/\mathbb{Q}$ is monogenic or not, and if so, to give me a defining polynomial for the integral ...
- 20.4k
4
votes
0
answers
102
views
Reconstructing coefficients of an elliptic curve L-series from the modular form divisor
Let $E$ be an unknown elliptic curve over $\mathbb{Q}$.
Let $L(E, s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$ be the L-function of $E$ and write $f(q) = \sum_{n=1}^{\infty} a_n q^n$.
I'm in a setting ...
- 5,637
9
votes
1
answer
737
views
Square root in number field
I'm trying implement an algorithm that, for an element $b$ of a number field $\mathbb{Q}(\alpha)$, if it is a square in $\mathbb{Q}(\alpha)$ (i.e., $\exists x\in\mathbb{Q}(\alpha):x^2=b$), computes ...
- 4,746
0
votes
0
answers
172
views
An application of Koike's Trace Formula
Koike's Trace Formula states that
\begin{equation}
\mbox{Tr}((U_p^{\kappa})^n) = - \sum_{0 \leq u < \sqrt{p^n}\\
(u,p)=1}H(u^2-4p^n)\frac{\gamma(u)^\kappa}{\gamma(u)^2 - p^n}-1,
\end{equation}
...
1
vote
1
answer
240
views
Software tools to find square root modulo $2^t$
Are there any software tools to find modular square roots of $y$ in $$x^2\equiv y\bmod p^t$$ where $p$ is a prime $\geq2$?
Are there any special techniques which can speed up at $p=2$?
- 34.3k
6
votes
1
answer
647
views
How can I efficiently find the "simplest" rational in an interval?
For a hobby software project I am working with exact rational arithmetic, as it happens this produces numbers $\frac{n}{k}$ of huge size even after reducing them, I am searching for an efficient ...
- 32.5k
0
votes
1
answer
63
views
Changing base field for sum of polynomials
Let $L/\mathbb{Q}$ be a finite extension and $f_{1},\dotsc,f_{n}\in L[x_{1},\dotsc,x_{k}]$ be degree $d$ homogeneous polynomials. Is there a way to find homogenous degree $d’$ polynomials $g_{1},\...
- 109k
3
votes
1
answer
128
views
Computational Theory problem
Is it possible to have a Turing machine that can compute an ODE equation (ordinary differential equation)?. If there is, then can you explain how can it compute.
- 188k
11
votes
1
answer
646
views
Non-trivial solutions for $-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac)$?
Consider the quartic system in four variables $a,b,c,d\in\mathbb R$:
$$-(c^2-d^2)(a^2-b^2)=2(ad-bc)(bd+ac).$$
Does this system admit rational solution with $$abcd(c^2-d^2)(a^2-b^2)(a^2-c^2)(b^2-d^2)\...
- 13.9k
2
votes
0
answers
118
views
Computing coefficients of theta functions associated to quadratic forms
If we take an integral positive definite quadratic form $Q$ and set $\Theta_Q(z) = \sum_{k\geq 0}R_Q(k)e^{2\pi ikz}$, what are the most efficient algorithms to compute the $R_Q(k)$? I am aware e.g. of ...
- 20.4k
5
votes
3
answers
2k
views
Square root algorithm
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
- 63.9k
4
votes
1
answer
995
views
Is there a way to specify a special kind of reciprocals of natural numbers?
Any number with of a form $\frac{1}{n}$ has a decimal with a repetend of finite length that is never longer than $n$ (provable by Dirichlet principle). (Example: $\frac{92}{99}=0.929292\ldots$ in ...
- 12.9k
2
votes
0
answers
300
views
How soon can we represent a number as the sum of two primes?
Posting in MO since it was unanswered in MSE.
Goldbach's conjecture says that every even number can be represented as the sum of two primes. But how soon can we find such a representation. Taking $20 =...
18
votes
1
answer
607
views
Complexity of a Fibonacci numbers discrete log variation
In my work I encountered the following
FIBMOD PROBLEM:
Given $k,m$ in binary, decide if there exists $n$ such that
$\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number.
This is a variation ...
- 4,713
0
votes
1
answer
87
views
Constructing an integer with small residues for two distinct primes in polynomial time
Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer
Is it ...
- 13.9k
2
votes
1
answer
171
views
On roots of irreducible quadratics modulo composites
Assume factorization of $N$ is unknown. What is the best complexity we know to find roots of the irreducible equation $$ax^2+bx+c\equiv0\bmod N?$$
Is this problem equivalent to any hardness results?
- 13.9k
4
votes
1
answer
308
views
Discrete logarithms and primitive elements in finite fields
The recent papers:
R. Granger, T. Kleinjung, J. Zumbragel, "On the Discrete Logarithm
Problem in Finite Fields of Fixed Characteristic," Trans. Amer. Math.
Soc., 370(5) (2018), 3129–3145.
T....
- 10.4k
3
votes
2
answers
901
views
Efficiently finding the largest divisor of N less than sqrt(N)
Suppose you have a number
$$
N = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
and are looking for the largest divisor $d|N$ such that $d^2<N$ (that is, A060775$(N)$.) How can I efficiently find this $d$?
...
- 2,183
9
votes
3
answers
584
views
Why is there an unexpected increase in the density of certain types of Goldbach primes?
Note: Posted in MO since it was unanswered in MSE.
I was checking how quickly we can verify Goldbach's conjecture for a given even number $n$ and it was clear that searching backward starting from the ...
- 30.1k
1
vote
0
answers
84
views
How common are semiprimes with equally bitsized factors among semiprimes with equal bitsize?
I am curious about the following after having looked at the paper "Almost primes in almost all short intervals", theorem 3 says:
Almost all intervals $[x, x + \log^{3.51}{(x)}]$ with $x ≤ X$...
- 11
2
votes
1
answer
514
views
Eisenstein polynomial of totally ramified extension over $p$-adic field
Let $p\geq 3$ be a prime number, $K$ be a finite extension of $\mathbb{Q}_p$ with no non-trivial unramified subextension, $f(x)$ be an irreducible monic polynomial in $\mathcal{O}_K[x]$, making $L=K[x]...
- 549