Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
477 questions
6
votes
1
answer
617
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 ...
- 6,377
3
votes
1
answer
535
views
abc-conjecture and positive definite kernels, again?
One formulation of the abc-conjecture is:
$$\forall a,b \in \mathbb{N}: \frac{a+b}{\gcd(a,b)}< \operatorname{rad}\left ( \frac{ab(a+b)}{\gcd(a,b)^3}\right )^2 $$
Let us define:
$$K(a,b) := \frac{2(...
- 3,144
1
vote
1
answer
207
views
Calculating the value of periodic continued fractions with $a_i\in\lbrace 0,1\rbrace$
Question:
How can the value of continued fractions of the form
$$y:=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\begin{align}\ddots& \\ &a_{n-1}+\cfrac{1}{a_n+y}\end{align}}}}}$$
$$...
- 13.2k
0
votes
1
answer
126
views
Integer quadratic representation subject to discriminant minimization algorithm
Let $f(x)=ax^2+bx+c$ and $f(x)=n$. Is there an algorithm to choose $a,b,c$ such that the discriminant is minimized? Where $a,b,c,n,x$ are all integers.
More concretely, is there an algorithm to find $...
2
votes
1
answer
252
views
A weird property of odd positive integers $n$ with $\sigma(n)\sim2n $
When one looks at positive odd integers $n$ for which $|\sigma(n)-2n|\le\log n$, (sequence A088012) it appears that for all seven known numbers of this type the abundance, $\sigma(n)-2n$ is $\equiv 6\...
- 433
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.
13
votes
2
answers
741
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
4
votes
0
answers
66
views
Computing preimage of element under norm map of quadratic extension of $2$-adic fields
Let $F$ be a $2$-adic field, i.e. a finite extension of the $2$-adic numbers $\mathbb{Q}_2$. Suppose that I have a quadratic extension $E = F(\sqrt{d})$ of $F$. Given a unit $\alpha \in \mathcal{O}_F^\...
- 411
4
votes
1
answer
217
views
Is there a Bailey–Borwein–Plouffe (BBP) formula for $\gamma$ (euler-mascheroni constant)?
I was reading about BBP type formulas and there was a lot about $\pi$ and some $\log$'s. I started searching for some other constants and could find $2$ formulas for the catalan constant and learned ...
- 521
2
votes
1
answer
320
views
Can you confirm the positivity of a quantity involving the Stirling numbers of the first kind
Let $s(m,n)$ denote the Stirling numbers of the first kind. For $m,n\in\mathbb{N}$, define
\begin{equation}
\mathcal{Q}(m,n)=(-1)^n\sum_{\ell=0}^{2n} \binom{m+\ell-1}{m-1} s(m+2n-1,m+\ell-1)\biggl(\...
- 1,101
4
votes
1
answer
377
views
Find $\mathbb{Z}$-basis of module over Dedekind domain provided its pseudobasis
Let $K$ be number field of degree $d$. Suppose we are given module $
\mathcal{M}$ in form:
\begin{equation}\label{key}
\mathcal{M} = v_1 \cdot \mathfrak{a}_1 \oplus v_2 \cdot \mathfrak{a}_2 \...
5
votes
1
answer
311
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.9k
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 ...
- 19.1k
0
votes
0
answers
145
views
Positive definite quadratic form algorithm
Let $f(x,y)= ax^2+bxy+cy^2$, or similarly denote it by $(a,b,c)$. This question is about the case $(1,0,p)$ where $p$ is prime. Suppose I have one solution $\bar{x}_1=(x_0,y_0)$ for $f(x,y)=m$ for ...
0
votes
1
answer
86
views
What can be said about $\gcd(N/q^{\alpha},\sigma(N/q^{\alpha}))$ where $N$ is an odd perfect number and $q^{\alpha} \parallel N$?
What can be said about the quantity $$\gcd(N/q^{\alpha},\sigma(N/q^{\alpha}))$$ where $N$ is an odd perfect number and $q^{\alpha} \parallel N$? In particular, can one prove that it is always greater ...
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
4
votes
3
answers
698
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+\...
- 1,101
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(...
- 53
26
votes
3
answers
2k
views
Sum of squares and divisibility
Consider an integer of the form $$N = 1 + \sum_{i=1}^r d_i^2$$ where $d_i \in \mathbb{N}_{\ge 3}$ and $d_i^2$ divides $N$.
Question: Must $r$ be greater than or equal to $9$?
Checking (with SageMath): ...
4
votes
0
answers
143
views
Road map for learning about the computational/general theory of modular curves/isogenies of abelian varieties for cryptography
I am a graduate math/crypto student. So I've had some free time last year and I heard about elliptic curves in cryptography and how a resilient cryptosystem got demolished by a spectacular attack ...
- 41
6
votes
0
answers
234
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 ...
- 591
0
votes
0
answers
185
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 ...
- 3,319
-2
votes
2
answers
149
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$.
- 577
2
votes
1
answer
547
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.9k
2
votes
0
answers
71
views
Simultaneous computation of the three Weber modular functions
Recall that the three classical Weber modular functions are defined by
$f(\tau)=e^{-\pi i/24}\eta((\tau+1)/2)/\eta(\tau)$,
$f_1(\tau)=\eta(\tau/2)/\eta(\tau)$, and
$f_2(\tau)=\sqrt{2}\eta(2\tau)/\eta(\...
- 13.1k
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 ...
- 2,649
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 ...
- 495
8
votes
1
answer
531
views
How large can the dimension of a 'Span of powers of a finite field basis' be?
Let $p$ be a prime. For finite field $\mathbb{F}_{p^k}$ and $d\in\mathbb{Z}^+$, I am considering the following quantity, where we interpret the field $\mathbb{F}_{p^k}$ also as a $\mathbb{F}_p$-vector ...
- 89
0
votes
1
answer
109
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, ...
0
votes
0
answers
319
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 ...
0
votes
0
answers
363
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
5
votes
2
answers
377
views
Reliability of ILP approach to number-theoretic optimization
This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...
- 34.4k
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 ...
- 211
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 ...
- 71
34
votes
1
answer
1k
views
Does any cubic polynomial become reducible through composition with some quadratic?
What I mean to ask is this:
given an irreducible cubic polynomial $P(X)\in \mathbb{Z}[X]$ is there always a quadratic $Q(X)\in \mathbb{Z}[X]$ such that $P(Q)$ is reducible (as a polynomial, and then ...
- 5,103
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 ...
- 565
3
votes
1
answer
1k
views
Coppersmith bivariate polynomial roots implementation
Given $f(x,y)\in\mathbb Z[x,y]$ Coppersmith in https://link.springer.com/chapter/10.1007%2F3-540-68339-9_16 provides a provable method to find integer roots in polynomial time and this method was also ...
- 13.9k
4
votes
1
answer
362
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 ...
- 73
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 ...
- 5,470
15
votes
2
answers
2k
views
Question on the 52nd (known) Mersenne prime number
In a footnote to the list of known Mersenne prime numbers which can be found here, we read that the "ranking" therein is a provisional one since not all possible exponents between $57 \, 885 ...
- 8,842
2
votes
0
answers
221
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.9k
1
vote
0
answers
136
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.9k
9
votes
1
answer
720
views
Is there a polynomial time algorithm for finding primes?
I was wondering if, given $k$, there is a deterministic polynomial time algorithm (polynomial in $k$) which finds a prime number with $k$ digits.
There is clearly a probabilistic one: just take random ...
- 1,251
6
votes
2
answers
310
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 ...
- 207
3
votes
2
answers
902
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$?
...
- 9,114
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 ...
- 163
4
votes
1
answer
723
views
Efficient computation of $\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor$
I need to compute efficiently the sum
$$
\sum_{i=1}^{\sqrt{n}} i^2\cdot\left\lfloor{\frac n{i^2}}\right\rfloor.
$$
We can do this in $O({\sqrt{n}})$ but I need a faster algorithm: for example, it ...
- 43
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 (...
- 4,786
9
votes
1
answer
738
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 ...
- 153
1
vote
0
answers
64
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