Questions tagged [computational-number-theory]
Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.
476 questions
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 ...
CommunityBot
- 1
0
votes
0
answers
61
views
Is the new method used by the GIMPS project applicable to non-Mersenne primes?
For years, there was a simple reason why the largest known prime is of the form $2^{p}-1$: We had the Lucas-Lehmer test which was specific to Mersenne numbers, and faster than all other known methods.
...
- 233
1
vote
0
answers
116
views
Can all congruences for a third-order recurrence relation hold for some composite $n$?
Let $p$ be a prime with $p \gt 3$. Consider the polynomial $f = x^3 - 3x -1$. Suppose $f$ is irreducible over $\mathbb{F}_{p}$. Let $E$ be the splitting field of $f$ over $\mathbb{F}_{p}$, and let $\...
2
votes
0
answers
161
views
Compute generators for group of totally positive units of a number field?
Given a number field $K$, I would like to compute (in Sage) generators for the group of totally positive units of $K$.
Update: I've tried some code (details below), which I've received some help on in ...
- 47.4k
-1
votes
0
answers
73
views
Analog of ceil and floor of $\sqrt{a(a+1)}$ in modular arithmetic
If we take ceil and floor of $\sqrt{x(x+1)}$ (when it exists) we get $x$ and $x+1$ respectively. Is there an analog of this assuming roots exist in modular arithmetic (at least modulo primes)?
...
- 13.9k
1
vote
1
answer
240
views
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$.
is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time?
if $a$ is ...
- 651
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
5
votes
1
answer
172
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$-...
4
votes
2
answers
609
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$
$...
- 1,091
34
votes
0
answers
1k
views
Is $2\uparrow\uparrow\infty + 3$ divisible by a prime number?
Define power tower using Knuth's arrow: $$a\uparrow\uparrow b=\left.a^{a^{a^{...^a}}}\right\}b\text{ layers}$$
It can be proved that for any positive integers $a, n, m\ \ $,
$\lim_{n \to \infty} a \...
- 24.2k
6
votes
1
answer
303
views
New Mersenne prime and compute time [closed]
GIMPS has just announced that $2^{136,279,841}-1$ is prime. Does anyone have a sense of the scale of the computational resources involved in finding this? (And maybe how it compares to, say, ...
- 82.7k
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
0
votes
0
answers
78
views
Is there an asymptotic expansion for the reciprocal of the classical Euler beta function?
The classical Euler beta function can be defined by
$$
B(p,q)=\int_0^1t^{p-1}(1-t)^{q-1}\operatorname{d\!}t
$$
for $\Re(p),\Re(q)>0$.
The beta function and the classical Euler gamma function $\...
- 1,091
93
votes
3
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 ...
- 161
4
votes
1
answer
376
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 \...
CommunityBot
- 1
1
vote
0
answers
114
views
Simultaneous elimination of variables in multiple polynomials
I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ ...
- 13.9k
-1
votes
1
answer
342
views
Finite or polynomial number integral points clarification on Coppersmith's theorems (possibility of ellipse counter example?)
Coppersmith states if $f(x,y)$ is an irreducible bivariate with total degree $\delta$ then if he can list all roots $(X,Y)$ of the polynomial in $\mathsf{poly}(\log D,\delta)$ time if the roots ...
- 13.9k
2
votes
1
answer
456
views
Integrality certification for product of two matrices $A B^{-1}$
Let's consider two non-singular integer matrices $A,B \in\mathbb{Z}^{n\times n}$. I want a test to check if $A\times B^{-1}$ is integral (or no denominators). I am referring the unimodular ...
CommunityBot
- 1
3
votes
1
answer
203
views
Chowla's theorem on class number of real quadratic field
Let $p\equiv1\bmod 4$ be a prime number and $h$
the class number of real quadratic field $\mathbb Q(\sqrt{p})$, $\epsilon=\frac{t+u\sqrt{p}}{2}$ its fundamental unit. In this paper https://www.pnas....
- 7,193
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 ...
- 34.3k
1
vote
0
answers
62
views
A conjecture on members of Lucas sequences not being pseudoprimes
Following conjecture on an infinite set of numbers satisfying the PSW-conjecture might be of academic interest in the understanding thereof.
Would you have any pointers on how to prove or disprove ...
1
vote
1
answer
73
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 ...
- 3,009
2
votes
1
answer
157
views
$f(x)\bmod p$ and decomposition of prime ideals
While reading Serre's beautiful book Lectures on $N_X(p)$, I thought of a related question.
Let $f(x)\in \mathbb{Z}[x]$ be a monic irreducible polynomial with integer coefficients. Let $K$ be the ...
- 105k
5
votes
1
answer
303
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 ...
- 12.9k
35
votes
9
answers
9k
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 ...
- 39.9k
3
votes
1
answer
513
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 ...
- 47.1k
3
votes
3
answers
293
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,370
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 ...
- 6,367
3
votes
1
answer
261
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)$$
...
- 5,382
1
vote
2
answers
383
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
$$
...
- 1
5
votes
0
answers
141
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,215
2
votes
1
answer
108
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?
- 2,183
14
votes
2
answers
683
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$ ?
- 79.9k
2
votes
0
answers
54
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 ...
- 83
2
votes
0
answers
52
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/\...
- 83
2
votes
0
answers
146
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}^{...
- 451
2
votes
0
answers
107
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 ...
- 869
0
votes
0
answers
61
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 ...
- 87
2
votes
0
answers
119
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
187
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 ...
- 1,087
2
votes
0
answers
187
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 ...
CommunityBot
- 1
11
votes
2
answers
1k
views
Do consecutive integers have a big prime factor?
Let us say that three consecutive positive integers $(m-1,m,m+1)$ have a big prime factor if the largest prime factor $p$ of $N=(m-1)m(m+1)$ satisfies $e^p>N$.
I ckecked that it is true for all $m&...
CommunityBot
- 1
45
votes
1
answer
6k
views
How to calculate [10^10^10^10^10^-10^10]?
How to find an integer part of $10^{10^{10^{10^{10^{-10^{10}}}}}}$? It looks like it is slightly above $10^{10^{10}}$.
CommunityBot
- 1
10
votes
2
answers
3k
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,\...
5
votes
2
answers
331
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:\...
- 14k
4
votes
0
answers
821
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 ...
- 11
3
votes
1
answer
386
views
Hermit H-machines
I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H.
Is there a ...
- 236k
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,391
2
votes
2
answers
1k
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 ...
- 127
2
votes
1
answer
158
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 ...
- 621