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
2
votes
0answers
52 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?
-2
votes
0answers
119 views

Showing primality of $1\bmod4$ integers

If $p$ is an integer that is $1\bmod 4$ and we know a representation of $p$ in the form $p=a^2+b^2$ then is there a deterministic polynomial time algorithm to conclude primality or not of $p$ without ...
1
vote
1answer
109 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 ...
1
vote
2answers
86 views

For a given value of $n$ and $m$, find $\text{fib}(n)$ $\text{mod } m$ where $n$ is very huge. (Pisano Period) [closed]

Input Integers $'n'$ (up to $10^{14}$) and $'m'$(up to $10^3$) Output $\text{Fib}(n)$ $\text{modulo}$ $m$ My questions For example : Why $\text{fib}(n=2015)$ $\text{mod}$ $3$ is equivalent to $\...
2
votes
0answers
91 views

Double Diophantine approximation

Let $0 < \alpha < 1$. For any $n$ there is a closest lower Diophantine approximation $\max p / q \leq \alpha$ with integer $0 \leq p < q \leq n$. It can be found efficiently, e.g., with Stern-...
1
vote
0answers
64 views

On the smallest solution of a linear congruence

I have the following question. First, consider the following congruence for primes $p\geq 5$: $24x\equiv -1\;(\mbox{mod}\;p)$. The smallest $x$, that is, $1\leq x\leq p-1$ for which the above ...
3
votes
1answer
251 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
votes
0answers
71 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 ...
1
vote
0answers
296 views

Finding elliptic curve with $P=[m]R$

To avoid X-Y problem I am going to write my problem down in detail, so plz bear with me. The elliptic curve over $Q$ given by a Weierstrass equation is - $E := y^2 +a_1 xy +a_3 y = x^3 + a_2 x^2+...
1
vote
0answers
72 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 ...
2
votes
0answers
227 views

The irrational numbers α such that n odd and m=⌊nα⌋ odd implies ⌊mα⌋ odd

This post is the analogous of that one (about $\sqrt{2}$) but with a much stronger expectation here. We observed, and then this comment of Lucia proved, that for $\phi$ the golden ratio, if $n$ ...
21
votes
2answers
1k views

Unexpected behavior involving √2 and parity

This post makes a focus on a very specific part of that long post. Consider the following map: $$f: n \mapsto \left\{ \begin{array}{ll} \left \lfloor{n/\sqrt{2}} \right \rfloor & \...
7
votes
0answers
384 views

Borderline Collatz-like problems

The usual Collatz map is $C:n \mapsto n/2$ if $n$ even, $(3n+1)/2$ if $n$ odd. Let $f^{\circ (r+1)}:=f \circ f^{\circ r}$. We suspect that for every fixed $n>0$, the sequence $C^{\circ r}(n)$ ...
12
votes
0answers
695 views

Why am I unable to find primes of the form $(9n)!+n!+1$?

See also Math StackExchange: Is there a prime of the form $(9n)!+n!+1$? Recently, user Peter from Math StackExchange asked for a prime of the form $(9n)!+n!+1$ (where $n$ is some natural number). ...
6
votes
0answers
251 views

Effective bounds for Fermat's Last Theorem

Suppose $n>2$. By Fermat's Last Theorem, we know that $a^{n}+b^{n}=c^{n}$ has no non-trivial solutions. Can we quantify it more? More specifically, given $a,b,c,n\in\mathbb{N}$ with $n>2$ and $...
6
votes
0answers
223 views

Brief history of primality testing theory after 2002?

Its clear that there is about 15 years (2004-2019) after the publication of AKS primality testing in 2002 and its modifications in 2003-2004. AS result, is there any development happened in this ...
2
votes
1answer
76 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\...
3
votes
0answers
132 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 ...
4
votes
0answers
239 views

All digits of $2^n$ are even if and only if $n=1,2,3,6,11$ [closed]

All digits of $2^n$ are even if and only if $n=1,2,3,6,11$. For example, $2^1=2,2^2=4,2^3=8,2^4=16,2^5=32,2^6=64,\ldots,2^{11}=2048,2^{12}=4096$. Do you know a proof of this fact or some related ...
3
votes
1answer
152 views

How can we justify the use of Example 5,4 (of Cohen, Lenstra) assuming their heuristics

In these days, I'm studying Cohen-Lenstra heuristics to understand the paper of Rene Schoof "Class Numbers of Real Cyclotomic Fields of Prime Conductor". On page 932 of Schoof's paper, there is a ...
1
vote
1answer
91 views

About another potential characterization of normal numbers

Normal numbers, in a nutshell, are real numbers that have a "uniform" distribution of digits in standard numeration systems (binary, decimal, and so on.) You can find a formal definition and ...
3
votes
0answers
162 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 ...
3
votes
0answers
71 views

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
7
votes
0answers
254 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 $...
0
votes
0answers
96 views

If the coefficient of the polynomial positive

I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$ $$\bar{S}(k)=\...
4
votes
0answers
86 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 ...
1
vote
1answer
86 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 ...
2
votes
0answers
131 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 ...
2
votes
2answers
185 views

How can I find explicit examples of maximal orders of quaternion algebras that are not isomorphic?

I know that there exist algorithms that will construct maximal orders of a quaternion algebra over, say, $\mathbb{Q}$. However, the implemented algorithms that I know of require that you input an ...
4
votes
2answers
221 views

Quadratic diophantine equations and geometry of numbers

Let (for concreteness) $a = 2$, $b = \sqrt{5}$ and $\varphi = (\sqrt{5}+1)/2$. I am interested in solutions $(w,x,y,z) \in \mathbb{Z}[\varphi]^4$ of the system $$ w^2 - ax^2 -by^2 + abz^2 = 1 $$ $$ \...
0
votes
0answers
62 views

Generating the digits in a base system by repeated multiplication of a number

The first 15 terms of the sequence {a_i} = 2^i are 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768. All of the digits in base-10, i.e. {0, ...
2
votes
0answers
66 views

Accelerating convergence of a product by multiplying by zeta values: history?

Let $R(s_1,\dotsc,s_n) = \prod_p r(p^{-s_1},\dotsc,p^{-s_n})$, where $r$ is a rational function on $n$ variables. Say we want to compute the value of $R(s_1,\dotsc,s_n)$ for some choice of $s_1,\dotsc,...
3
votes
1answer
359 views

Yet another question on sums of the reciprocals of the primes

I recall reading once that the sum $$\sum_{p \,\, \small{\mbox{is a known prime}}} \frac{1}{p}$$ is less than $4$. Does anybody here know what the ultimate source of this claim is? Please, let me ...
2
votes
1answer
129 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 $$\...
1
vote
0answers
107 views

Testing polynomials irreducible over the integers

Let $f\in\operatorname{int}(\mathbb Z)$, the ring of integer-valued rational polynomials. Define $\operatorname{P}^+(f)$ as the number of primes $>0$ that $f$ assumes at distinct integral arguments....
2
votes
1answer
215 views

Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]

I need to emulate this sequence for a program: http://oeis.org/A025302 Stuff that I've taken into account: After finding the prime divisors of a number. I take any divisor as p and apply the ...
0
votes
0answers
54 views

Quadrics over the univariate function field with discriminant of minimal degree

Consider a non-degenerate quadric $Q(x,y,z) \subset \mathrm{P}^2$ over the univariate function field $\mathbb{F}_p(t)$, where $\mathbb{F}_p$ is a prime finite field, $p > 2$. For simplicity assume ...
1
vote
1answer
130 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 ...
3
votes
1answer
205 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+\...
5
votes
0answers
181 views

Is there some computational evidence of the $pq$ analog of Serre's conjecture?

The $pq$ analog of Serre's conjecture (see "Mod pq Galois representations and Serre's Conjecture"- Khare, Kiming) states that if $\bar{\rho}_1:G_{\mathbb{Q}}\rightarrow \text{GL}_2(\mathbb{F}_p)$ is a ...
-1
votes
1answer
442 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 ...
3
votes
1answer
90 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?
2
votes
0answers
95 views

Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?

We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
0
votes
1answer
559 views

Conjecture that relates matrix systems with some specific functions as solution sets

what is written below is a conjecture that I posed , and I ask for a proof or a disproof of it .I have checked the conjecture from $n$=$1$ up to $n$=$10$ using Matlab, and all results were in ...
11
votes
2answers
377 views

Extension of Dickson's theorem on integers of the form $a^2+b^2+2c^2$

Theorems V in this paper of L.E. Dickson states that the following two sets are equal. $$E=\{a^2+b^2+2c^2 \ | \ a,b,c \in \mathbb{Z}\} \ \text{ and } \ F=\mathbb{N} \setminus \{4^k(16n+14) \ | \ k,n \...
2
votes
1answer
146 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$...
4
votes
1answer
236 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 ...
1
vote
0answers
25 views

Uncertainty in semiprime factors

What is maximum $p\in(0,\frac12)$ such that if we know $2p\in(0,1)$ fraction of bits of $PQ$ with $P,Q$ primes it is possible to identify $p$ fraction of bits in each of $P,Q$ with certainty in ...
17
votes
4answers
644 views

In which cyclic cubic number fields does there exist this type of unit?

Let $K$ be a cyclic cubic number field with conductor $f$ and ring of integers $\mathcal{O}_K$. Define $K$ to be blue if and only if $$\operatorname{Norm}_{K/\mathbb{Q}}(w) = \operatorname{Norm}_{K/...
1
vote
1answer
380 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 ...

1
2 3 4 5 6