Skip to main content

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
3 votes
0 answers
73 views

Reference: Asymptotic bit-complexity of algebraic operations and transcendental functions

This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that ...
Eric Inclan's user avatar
6 votes
2 answers
698 views

existence of an elliptic curves with given number of points over finite field

Is there a theorem which guarentees the existance of an elliptic curve with given number of points over $\mathbf{F}_p$ for a given $p$. Thanks
Himanshu Shukla's user avatar
3 votes
0 answers
110 views

Minimum of a product of polynomial evaluated at primitive roots of unity, given that the value of the polynomial at the same lies on unit circle

This is something that came out of working on a problem: Let $m$ be an odd positive integer and $f \in \mathbb Q[x]$ be a polynomial of degree less than $m$. With $\zeta_m$ denoting a primitive root ...
asrxiiviii's user avatar
2 votes
0 answers
54 views

Asymptotic growth of the collection of Miller-Rabin pseudo-primes witnessed by a set

Consider a set $S$ of positive integers[*]. Define $P(S)$ as the set of numbers $N$ for which elements of $S$ are "witnesses" for the Miller-Rabin test for primality of $N$. Explicitly $P(S)=...
Kapil's user avatar
  • 1,566
12 votes
1 answer
308 views

Factoring polynomials over the abelian closure of the rationals

What algorithms are known to perform the following task? Input: a univariate polynomial over the rationals $f \in \mathbb{Q}[t]$. Output: the factorization of $f$ into irreducible factors over the ...
Gro-Tsen's user avatar
  • 32.5k
2 votes
0 answers
93 views

Elementary Iwasawa module

Let $k$ be a given number field. What is the importance and applications of knowing that the Iwasawa module $X_\infty$ of $k$ is an elementary $\Lambda$-module?
dekster's user avatar
  • 21
7 votes
0 answers
274 views

Are there infinitely many zeroes of $\sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) $?

Let $\mu(n)$ be the Möbius function and $S(x)$ be the number of positive integers $n \le x$ such that $$ \sum_{r = 1}^{n-1} \mu(r)\gcd(n,r) = 0 $$ My experimental data for $n \le 6 \times 10^5 $...
Nilotpal Kanti Sinha's user avatar
-1 votes
1 answer
725 views

summation of Euler totient function

Let $\phi(n)$ be the Euler totient function and let $2\leq k\in\mathbb{N}$. For $m\in\mathbb{N}$, are there any known results, upper bounds (tighter than just removing the coprimality) or ...
Nick A. R.'s user avatar
8 votes
3 answers
2k views

Numerical evaluation of the Petersson product of elliptic modular forms

It is known how to compute the Fourier expansion of elliptic modular forms using modular symbols, and it is known how to get numerical evaluations of $L$-functions of various type ; it's possible to ...
13 votes
1 answer
1k views

An efficient isomorphism between finite fields

Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic ...
Alexey Milovanov's user avatar
5 votes
1 answer
610 views

Eulerian ordering of the integers modulo n

Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$. An Eulerian ordering of $C_n$ is an ordering $r_1, \dots, r_n$ of its elements such that: $$\forall i \le n \ \forall j&...
Sebastien Palcoux's user avatar
6 votes
0 answers
93 views

Computing all eta quotients of given weight and level

I have written a rather naive program for finding all holomorphic eta quotients of given weight and level (and varying character). When the level has few divisors it is very fast, but incredibly slow ...
Henri Cohen's user avatar
  • 13.1k
3 votes
0 answers
189 views

Largest observed value of $S(t)$

Let $S(t)$ be the deviation of the number of zeros of the Riemann zeta function up to height $t$ from the expectation. What is the largest observed value of $S(t)$ today? Here is a quote from a ...
Farzad Aryan's user avatar
4 votes
0 answers
182 views

Computing the density of a set of multiples

Erdős and his coauthors often wrote about problems relating to the densities of sets of multiples. I have a computational question about the same topic. I have a finite* set $A=a_1<\cdots<a_r$ ...
Charles's user avatar
  • 9,114
15 votes
4 answers
2k views

Computing minimal polynomials using LLL

I would like to use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL algorithm) to compute the minimal polynomial of a (real) algebraic number $\alpha$ from a decimal approximation $a$...
Mark Bell's user avatar
  • 3,165
2 votes
1 answer
199 views

Decide if a system of arithmetic sequences is an $m$-cover of $\mathbb{N}$

Let $A = \{ a_i + b_i \mathbb{N} \}_{i=1}^{k}$, where $a_1, \ldots, a_k \in \mathbb{N} \cup \{0\}$ and $b_1, \ldots, b_k \in \mathbb{N}$ be a system of arithmetic sequences. For a positive integer $m$...
Victor's user avatar
  • 655
2 votes
1 answer
89 views

Partitioning integers into two parts and exploring relationships with positional numeral systems

I asked this question in Mathematics StackExchange (link) about a month ago, but I have received no answer. It is about the following problem: Problem: Are there sets $A,B$ of integers such that $A\...
C. Fujinomiya's user avatar
2 votes
1 answer
235 views

How to get asymptotic expansion of the sum of modified Bessel function $\sum_{n=1}^\infty K_0(s\, n)$ as $s\to 0^+$?

I guess for the modified Bessel funcion $K_0(z)$, $$\sum_{n=1}^\infty K_0(s\, n) \sim \frac{-2\log 2 - \log \pi + \gamma}{2} + \frac{\log s}{2} + \frac{\pi}{2\, s}, \quad s\to 0^+,$$ if taking $$\...
Rui's user avatar
  • 21
2 votes
1 answer
416 views

How hard is it to compute these prime factor related problems?

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?). Let $\omega(n)$ be number of distinct ...
Turbo's user avatar
  • 13.9k
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 ...
Hermite's user avatar
  • 77
3 votes
2 answers
332 views

On generating squarefree integers and primes?

Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known deterministic algorithms to sample $O(n^\alpha)$ (not just get one) square free integers of $n$ bits? Is it $O(n^{\alpha})$ complexity? ...
Turbo's user avatar
  • 13.9k
3 votes
1 answer
238 views

Norm of a Vector in a Number Field (or Order in a Number Field)

I am looking for a measurement, which gives a length of a vector in a number Field? Is there any way or definition for that. For the Maximal order, What if, I tried to define a map from Maximal order ...
student's user avatar
  • 149
4 votes
1 answer
288 views

Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?

The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
Turbo's user avatar
  • 13.9k
4 votes
0 answers
189 views

How to find a CM point with the image in the elliptic curve under modular parametrization given

everyone! Let $E:y^2+y=x^3-61$ be the minimal model of the elliptic curve 243b. How can I find the CM point $\tau$ in $X_0(243)$ such that $\tau$ maps to the point $(3\sqrt[3]{3},4)$ under the modular ...
yhb's user avatar
  • 390
2 votes
2 answers
257 views

Reference request for function by which to compute coefficients of continued fraction of algebaic number

The simple continued fraction is in the form $$[1;1,2,3,4,5,\dots]=1+\cfrac{1}{1+\cfrac{1}{2+\cdots}}, $$ for instance. Obviously,the coefficients $x_i$can be computed by computable function $x_i=f(i),...
XL _At_Here_There's user avatar
1 vote
0 answers
77 views

Digit summation of squared numbers

In olympiad teaching period, we have a session that students must try to design a good problem for others. Many times we arrive to good questions but sometimes there are some challenges. In one of our ...
Shahrooz's user avatar
  • 4,784
1 vote
1 answer
465 views

Taking pairwise coprime integers from prescribed sets

Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist? Given $m$ and $n$ in $\mathbb Z_{>0}$ what ...
Turbo's user avatar
  • 13.9k
15 votes
2 answers
1k views

Sum of $\sum_{k=1}^nd(k^2)$

There is a literature dealing with $$ \sum_{k\le x}d(f(k)) $$ where $f$ is an irreducible polynomial and $d(n)$ is the number of divisors of $n$. Erdos 1952 shows that the sum $\asymp x\log x,$ which ...
Charles's user avatar
  • 9,114
5 votes
2 answers
1k views

Is there a Bailey–Borwein–Plouffe (BBP) formula for e? [duplicate]

I recently used Bailey–Borwein–Plouffe formula to implement a π digit generator. Now I also want to implement an e digit generator, for the Euler number. I've ...
user avatar
7 votes
1 answer
382 views

Counting twin primes efficiently

This question, as well as its answers and comments, highlights a lot of unsettling numerical coincidences where certain sums over twin primes ostensibly converge to all kinds of weird values, however ...
Mikhail Tikhomirov's user avatar
6 votes
2 answers
323 views

Computing the relative class group (with Galois action) of relatively large cyclotomic groups

For a cyclotomic field $K = \mathbb Q(\zeta_n)$, let $K^+$ be its maximal totally real subfield. We know that $H^+ = Cl(K^+)$ injects into $H = Cl(K)$. I am interested in computing the group $H/H^+$ ...
Asvin's user avatar
  • 7,746
5 votes
1 answer
354 views

Fastest deterministic factoring algorithm in subexponential space?

Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-...
Dan Brumleve's user avatar
  • 2,302
12 votes
1 answer
547 views

Seeking references for finding primes infinitely often

I've been pondering this weakened version of the finding primes problem for a while: Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$? This differs from ...
Dan Brumleve's user avatar
  • 2,302
11 votes
2 answers
1k views

Why going to number fields in number field sieve help beat quadratic sieve?

To factor an $n$ bit integer number field sieve roughly takes $$e^{c{(\ln\ln n)^{\frac23}}({\ln n})^{\frac13}}$$ time while quadratic sieve takes $$e^{c{(\ln\ln n)^{\frac12}}({\ln n})^{\frac12}}$$ ...
user avatar
3 votes
1 answer
293 views

Number of lattice points on spheres with center not at the origin

Let $k\ge1$. It is known that the number of lattice points on the $k$-sphere $S^k(0)$ (center at the origin, radius $R$), namely the size of $\mathbb{Z}^{k+1}\cap S^k(0)$, is bounded by $R^{k-1+\...
Right's user avatar
  • 187
10 votes
2 answers
624 views

Computing millions of coefficients of non self-dual modular forms

To test some conjectures made by some colleagues, I need to compute millions of coefficients of non self-dual modular forms, preferably in low weight (say 2 or 3). A form such as this. For elliptic ...
ncr's user avatar
  • 361
5 votes
0 answers
179 views

Finding a presentation matrix with low dimension

Let $R=\mathbb Z[t^{\pm}]$ and $M$ a finitely generated $R$-module. With $A$ a presentation matrix, i.e we have the following exact sequence (usually I'm working with the case where $A$ is an square ...
bruno mazorra's user avatar
2 votes
0 answers
137 views

Compare my software's representation of exponential numbers and 0?

Suppose I have a real number $$ x=\sum_{i=1}^n a_i e^{\lambda_i} $$ where $a_i,\lambda_i$s are complex algebraic numbers. Is there an algorithm to determine whether it is greater than 0 or less than ...
gondolf's user avatar
  • 1,503
1 vote
1 answer
189 views

Explicit bivariate quadratic polynomials where Coppersmith is better than standard solver?

http://www.numbertheory.org/pdfs/general_quadratic_solution.pdf gives a general method to solve quadratic bivariate diophantine equation while Coppersmith introduced a method to solve bivariate ...
Turbo's user avatar
  • 13.9k
2 votes
0 answers
99 views

A problem in modular roots

We have three mutually coprime integers $r,t,M$ where $M\asymp K^{\frac12-2\epsilon}$ and $r,t\asymp K^{\frac14+\epsilon}$ holds with some fixed $\epsilon>0$ and $K>0$ is a large parameter. ...
Turbo's user avatar
  • 13.9k
5 votes
2 answers
314 views

Congruences for the non-divisors of Euler's $\phi(n)$

If $n$ is composite, then $\phi(n) < n-1$: hence, there is at least one number $d$ which does not divide $\phi(n)$ but divides$(n-1)$. We shall call $d$ the totient divisor of $n$. The purist will ...
Nilotpal Kanti Sinha's user avatar
4 votes
1 answer
283 views

Small roots of $f(x) \equiv 0 \pmod{n^2}$

Let $f(x)$ be squarefree polynomial with integer coefficients. For integer $n$ define "small root modulo $n^2$" integer $a$ satisfying $1 \le a \le n$ and $f(a) \equiv 0 \pmod{n^2}$ and $f(a) \ne 0$. ...
joro's user avatar
  • 25.4k
5 votes
2 answers
342 views

Methods to decide whether two positive definite ternary quadratic forms are in the same spinor genus?

Are there any effective methods to decide whether or not two positive definite ternary quadratic forms are in the same spinor genus? For example, the following three forms are in the same genus <...
whl likes fish's user avatar
1 vote
2 answers
347 views

Determining if a number is k-rough without factoring

A k-rough number is a natural number whose smallest prime factor is >= k, basically in opposition to the notion of a smooth number. Clearly, it's trivially easy to generate a k-rough composite number:...
Jeremy 's user avatar
  • 379
11 votes
3 answers
2k views

Mertens' function in time $O(\sqrt x)$

This MathOverflow question seems to indicate that the state of the art in computing $$ M(x)=\sum_{n\le x}\mu(n) $$ takes time $\Theta(n^{2/3}(\log\log n)^{1/3}),$ which matches my understanding. ...
Charles's user avatar
  • 9,114
11 votes
1 answer
3k views

Best way to find a closest vector in a lattice

Let $v_1,\dotsc,v_n$ be linearly independent vectors in $\mathbb{R}^n$, and let $\Lambda=\bigoplus_{i=1}^n \mathbb{Z}v_i$. The question is, given a vector $w$ in $\mathbb R^n$, find the element $v$ ...
David Cardon's user avatar
3 votes
1 answer
108 views

Is coprimality in $NC$?

Following reference https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf claims integer coprimality is in $NC$ and it also has one citation. Is this claim valid?
Turbo's user avatar
  • 13.9k
4 votes
1 answer
324 views

Higher roots modulo prime complexity best algorithm

Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$. What is the best method to find all such ...
Amal Duriseti's user avatar
1 vote
1 answer
144 views

Factoring with partial information on gaps

If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...
Turbo's user avatar
  • 13.9k
1 vote
1 answer
138 views

How to compute the Müller modular polynomials?

According to R.A.Kazmi's dissertation "Isogenies and Cryptography" (Page 22), given an isogeny degree $l$, the Müller modular polynomials are defined as $$G_l(x,y)=\sum_{r=0}^{l+1}\sum_{k=0}^{v}a_{...
Licheng Wang's user avatar

1
4 5
6
7 8
10