Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

Filter by
Sorted by
Tagged with
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 ...
Command Master's user avatar
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 ...
mtheorylord's user avatar
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 ...
user511994's user avatar
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{...
polygamma's user avatar
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, ...
ReverseFlowControl's user avatar
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 ...
Daniele Tampieri's user avatar
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$ ...
Turbo's user avatar
  • 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 ...
Turbo's user avatar
  • 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 ...
wjmccann's user avatar
  • 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 ...
Consider Non-Trivial Cases's user avatar
-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$.
C. Simon's user avatar
  • 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$ ...
Turbo's user avatar
  • 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\...
Turbo's user avatar
  • 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 ...
Leif Sabellek's user avatar
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+\...
qifeng618's user avatar
  • 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 ...
Turbo's user avatar
  • 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 ...
Lost in Traslations's user avatar
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?
Turbo's user avatar
  • 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\}...
Max Alekseyev's user avatar
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.
Yottakutta's user avatar
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 ...
Manuel Bravi's user avatar
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 ...
Manuel Bravi's user avatar
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 ...
Craig Feinstein's user avatar
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 ...
Turbo's user avatar
  • 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 $...
Turbo's user avatar
  • 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 $...
Turbo's user avatar
  • 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 ...
David Schwein's user avatar
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(...
Fran's user avatar
  • 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$ $...
qifeng618's user avatar
  • 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. ...
ReverseFlowControl's user avatar
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 $\...
Anish Ray's user avatar
  • 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 ...
Craig Feinstein's user avatar
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}...
gigi's user avatar
  • 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\...
Turbo's user avatar
  • 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 ...
Nilotpal Kanti Sinha's user avatar
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 ...
foivos's user avatar
  • 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 ...
domotorp's user avatar
  • 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 (...
Wlod AA's user avatar
  • 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 ...
Andrea B.'s user avatar
  • 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 ...
Asanovic Tomas's user avatar
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 $...
Nicolas Couture-Grenier's user avatar
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 ...
Turbo's user avatar
  • 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 ...
apeman's user avatar
  • 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 ...
MikeTeX's user avatar
  • 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 ...
Turbo's user avatar
  • 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 ...
crosscc's user avatar
  • 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 ...
XL _At_Here_There's user avatar
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 $<\...
Max Alekseyev's user avatar
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\...
Hvjurthuk's user avatar
  • 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 ...
Melanka's user avatar
  • 557

1
2 3 4 5
9