# Questions tagged [computational-number-theory]

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

463
questions

5
votes

1
answer

265
views

### Efficiently computing $\prod_{i=1}^{n} A_i$

Let $k$ be a nonnegative integer, how to compute $\prod\limits_{i=1}^{n} A_i$ quickly and accurately, where $$A_i=\begin{bmatrix}
0 & 1\\
i^k & 1
\end{bmatrix}?$$
I know if $k=0$, we can use ...

3
votes

1
answer

503
views

### Regarding the digit expansion of $\sqrt 7$

Let $\sqrt 7=\sum_{i=0}^\infty a_i 7^{-i}, 0\le a_i \le 6$ be the expansion of $\sqrt 7$ in base $7$.
I am curious about the following question: Is there a $K\in \mathbb{N}$ such that for any $n\ge ...

5
votes

0
answers

126
views

### Compute weight of modular form from its Fourier coefficients

It is known that Hecke eigenform $f \in S_{k}(\Gamma_0(N), \chi)$ is uniquely determined by first $C_{k,N}$ many Fourier coefficients, where $C_{k,N}$ is a constant only depends on $k$ and $N$. For ...

2
votes

1
answer

100
views

### On square root modulo $2^t-1$

Is there a way to compute an $x$ satisfying $$x^2\equiv a\bmod(2^t-1)$$ where $a,t$ are integers given to us and factorization of $2^t-1$ is not given to us?

5
votes

0
answers

101
views

### Isogenous elliptic curves and canonical modular polynomials

Let $\ell$ and $p$ be two primes. We are looking for a method for checking whether two supersingular elliptic curves over the finite field $F_p$, given through their $j$-invariants, are $\ell$-...

2
votes

0
answers

52
views

### Conductor of hyperelliptic curve after adding a rational root

Let $r\geq 5$ be a prime. Suppose I have a specified hyperelliptic curve $C: y^2=f(x)$ defined over $\mathbb{Q}$, where $f\in\mathbb{Q}[x]$ has degree $r$.
Note: the roots of $f$ are not rational but ...

14
votes

2
answers

675
views

### Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$?

Can four integer numbers $x$, $y$, $x-y$, $x+y$ be powerful numbers where $\gcd(x,y)=1$ ?

3
votes

1
answer

251
views

### Could efficient solutions of $x^2+n y^2=A$ be related to integer factorization?

Let $n$ be positive integer with unknown factorization and $A$ integer with known
factorization.
According to pari/gp developers pari can efficiently find all solutions of:
$$x^2+n y^2=A \qquad (1)$$
...

3
votes

3
answers

286
views

### Finding a prime which is a square modulo all small primes

I want to find a small prime $p$ satisfying
$p\equiv 1 \pmod{8}$
$\left(\frac{p}{q} \right) = 1$ for all primes $3 \leq q \leq N$
where $N$ is a moderately large number (say, around $15,000$). I ...

2
votes

0
answers

45
views

### Conductor of hyperelliptic curve after base change

Let $r\geq 5$ be a prime, and let $\zeta$ denote a primitive
$r$-th root of unity. Let $C$ be a hyperelliptic curve defined over $\mathbb{Q}$.
Suppose I have computed the conductor exponent $n$ of $C/\...

2
votes

0
answers

103
views

### Record for determining complete list of imaginary quadratic fields with small class number

In 2003, Mark Watkins (Class numbers of imaginary quadratic fields) determined all imaginary quadratic fields having class number at most 100.
Has this list been improved? That is, what is the largest ...

2
votes

0
answers

142
views

### Reference for accelerated sum to compute the Meissel-Mertens constant

The Meissel-Mertens constant
$$ B_1 = \lim_{n \to \infty} \left(\sum_{p \leq n} \frac{1}{p} - \log\log n\right) $$
has the series representation
$$
\begin{equation} \tag{1}
B_1 = \gamma + \sum_{n=2}^{...

0
votes

0
answers

60
views

### Is generating semirandom blake256 hashes until packed points is on the curve, a safe algorithm to avoid the discrete log between the generated points?

I know there are more robust methods, but I wanted to know about this specific one
For any distinct said randomly generated point : $P_i,P_j\in \{P_1,...,P_k\}$ it should be hard to find $s$ such that ...

2
votes

0
answers

112
views

### gcrd and associates of an element of the quaternion algebra over a totally real number field $K$

Let $K$ be a totally real number field of class number 1, and $Q$ the quaternion algebra over the ring of integers of $K$ with basis
$\{1,i,j,k\}$ such that $i^2 = j^2 = k^2 = -1$ and $ij = -ji, ik = ...

5
votes

0
answers

177
views

### Is there an effective way to compute the square root of an algebraic number?

For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...

2
votes

0
answers

176
views

### How to construct an explicit isomorphism of the split Quaternion Algebra $(a,b)_F$ over the field $F$ to $\mathrm{Mat}_2(F)$

$\DeclareMathOperator\Mat{Mat}$How to construct an explicit isomorphism of the split quaternion algebra $(a,b)_F$ over the field $F$ to $\Mat_2(F)$?
As it is known that the algebra of quaternions is ...

5
votes

2
answers

312
views

### Computing the Abelian invariants of a subgroup of a f.g. Abelian group

We have a f.g. Abelian group $A$ given as a direct sum of $N$ cyclic subgroups $C_{k_j}=\langle x_j\rangle$, with $k_j\in \{2,\dots,\infty\}$, $1\leq j \leq N$, and the associated homomorphism $\phi:\...

4
votes

0
answers

804
views

### One of the numbers $\zeta(5), \zeta(7), \zeta(9), \zeta(11)$ is irrational

I am reading an interesting paper One of the numbers ζ(5), ζ(7), ζ(9), ζ(11) is irrational by Zudilin. We fix odd numbers $q$ and $r$, $q\geq r+4$ and a tuple $\eta_0,\eta_1,...,\eta_q$ of positive ...

1
vote

0
answers

38
views

### Time complexity of Magma's `NormEquation` for quadratic extensions of $2$-adic fields

Note: This is similar to, but easier than, a previous question I asked here. It is a different question! I'm hoping this one might get an answer because it concerns a standard algorithm, whereas the ...

16
votes

2
answers

1k
views

### Is it decidable whether two real algebraic irrationals generate the same extension of the rationals?

For an algebraic number $\alpha$, let $f_\alpha$ denote its minimal polynomial. We can symbolically represent an algebraic number $\alpha$ by the tuple
$$
(f_\alpha, x, y, r) \in \mathbb{Q}[x] \times ...

2
votes

1
answer

150
views

### Are the coefficients in the stationary phase approximation computed explicitly somewhere

In Stein's "Harmonic analysis" book, page 334, one can find
the asymptotic expansion
An instructive proof is given for the case $k=2$. It is clear enough to generalize to the cases $k\geq ...

2
votes

2
answers

951
views

### Sum of three square is a square and sum of their product taken two at a time is also a square

Let $a^2 + b^2 + c^2 = X^2$ and
$$(ab)^2 + (ac)^2 + (bc)^2 = Y^2$$
Such that $a,b,c,x,y$ are all non zero Integers.
How to find All solutions ?
Is there any parametrization which gives Infinitely ...

1
vote

1
answer

95
views

### Number of solutions for linear modular equations given GCD

We are currently investigating a problem involving number theory, an area outside our field of expertise.
Let $n$ be a positive integer. Consider two pairs of integers $(j,k)$ and $(j′,k′)$ as ...

13
votes

2
answers

1k
views

### Using the Eichler-Selberg Trace formula to compute class numbers?

The Eichler-Selberg trace formula (Theorem 2.2 here) gives a relation between the trace of a Hecke operator acting on the space of cusp forms and sums of weighted class numbers of imaginary quadratic ...

4
votes

0
answers

59
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^\...

3
votes

1
answer

206
views

### Generators of the ideal class group

Theorem 4 of Eric Bach's "Explicit bounds for primality testing and related problems" states the following:
Let $K$ be a number field of degree greater than 1. Let $d$ be the absolute value ...

5
votes

0
answers

192
views

### Empirical bounds on $\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right|$

It is reasonable to expect that $$\left|\frac{\zeta'(1+it)}{\zeta(1+it)}\right| < 2 \log \log t$$
for all $t\geq 4$ (say): a somewhat stronger bound is known for $t\geq 10^{165}$ or so (Theorem 5 ...

4
votes

0
answers

321
views

### Are there infinitely many simple integral fusion rings of rank $4$?

$\DeclareMathOperator\ch{ch}$$\DeclareMathOperator\FPdim{FPdim}$We refer to [EGNO15, Chapter 3] for the notion of fusion ring and basic results. The type of a fusion ring $R$ is the list $(\FPdim(b_i)...

1
vote

2
answers

373
views

### Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?

Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that:
$$
f(n)=\sum_{d\mid n}d\varphi(d)
$$
and
$$
...

3
votes

2
answers

275
views

### When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for e [closed]

When I know the two points on an elliptic curve, and the two points satisfy the relationship: $Q=e \cdot P$, is it possible for me to solve for $e$.
The equation of the curve is: $y^2 = x^3 + ax + b \...

0
votes

1
answer

124
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 $...

0
votes

0
answers

62
views

### What is the lattice point distribution over binary quadratic forms?

Let $f(x,y)=x^2+ny^2$ be the binary quadratic form of interest and consider the lattice points $S=\{ (x,y,f(x,y)) \in \mathbb{N}^3 \}$.
For simplicity, we keep things only on quadrant I of the ...

5
votes

3
answers

350
views

### How to recover integer part from known fractional root part?

Suppose you have $r=n+f$ where $n\in\mathbb{N}$ and $f\in (0,1)$. I know that $r^2$ is an integer and I can also get as many digits of $f$ as I like, is there a way to recover the value of $n$?
Thank ...

3
votes

1
answer

289
views

### Does this condition characterise intervals, among subsets of the real line?

For a real number, $c\in \left]0,1\right[$, consider the following property $\mathbf(\mathbf P_c\mathbf)$ of subsets $A$ of $\mathbb R$:
$\mathbf(\mathbf P_c\mathbf)$ For every bounded set $B\subset \...

1
vote

1
answer

202
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}}}}}$$
$$...

2
votes

0
answers

70
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(\...

9
votes

2
answers

2k
views

### Can every integer be written as a sum of squares of primes?

This question is mainly inspired from a different problem I was working on.
Is there a value of $k$ such that, for each $n\in \mathbb N$, the equation
$$\sum_{i=1}^{k}x_i^2=n$$
is solvable in $x_1,\...

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 ...

0
votes

0
answers

143
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 ...

2
votes

1
answer

251
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\...

4
votes

1
answer

203
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 ...

2
votes

1
answer

313
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(\...

4
votes

0
answers

134
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 ...

0
votes

0
answers

184
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 ...

6
votes

0
answers

213
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 ...

1
vote

0
answers

56
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 ...

0
votes

0
answers

349
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{...

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, ...

6
votes

1
answer

613
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 ...

3
votes

1
answer

523
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(...