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
6 votes
2 answers
945 views

Minkowski successive minima inequality for a lattice base?

Let $\Lambda$ be a lattice of $\mathbb{R}^n$, and $\lambda_i$ be the radius of the smallest ball containing $i$ linearly independent lattice vectors. The Minkowski successive minima inequality says ...
Mostafa's user avatar
  • 403
1 vote
1 answer
351 views

Valid Difference Sets

Suppose $$ P \subseteq \{1,2,\dots,N\},\quad |P| = K $$ We calculate the differences as: $$ d=p_i-p_j\mod N,\quad i\ne j $$ Now let $a_d$ denote the number of occurrence of $d$ (for $d = 0, 1, 2, ...
Mahdi Khosravi's user avatar
2 votes
1 answer
385 views

Question on x coordinates of Mordell Curves where $y^2=x^3+k$ and $k^2 = 1$ mod $24$

In my ongoing search for Mordell curves of rank 8 and above I have currently identified 144,499 curves of a type where $k$ is squarefree and $k^2 = 1$ mod $24$. In each case the x coordinates are ...
Kevin Acres's user avatar
0 votes
1 answer
223 views

Spreading-out integers via multiplication

Let $a_1,...,a_n\in [0,m]$ be a set of $n$ positive integers, where $n<<m$, $m=poly(n)$. One can assume $m$ is prime. Is there an efficient, possibly randomized, way to find an integer $N=poly(n)...
Lior Eldar's user avatar
2 votes
2 answers
494 views

On Cubic Non-Residues Modulo a Prime [closed]

What is a good test for identifying cubic non-residues/residues and higher power non-residues/residues modulo a prime $R$ in terms of computational complexity? Given $M$ and $N$, is there a good way ...
Turbo's user avatar
  • 13.7k
5 votes
3 answers
2k views

Square root algorithm

I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
Richard Warren's user avatar
2 votes
0 answers
706 views

Textbooks on Algorithmic Number Theory

I am looking for a good textbook suitable for graduate or advanced undergraduate students who want to explore algorithmic number theory. Specifically, algorithms for primality testing, and factoring ...
Chebolu's user avatar
  • 575
0 votes
0 answers
433 views

Computational Ring Theory

I have tried to understand and program CGT algorithms though I am a beginner still. But I never get to hear Computational Ring Theory. Even GAP largely supports Groups Theory. Is there some initiative ...
Pankaj Sejwal's user avatar
4 votes
2 answers
504 views

Average involving the Euler phi function

Does $$\frac{1}{N^2}\sum _{d=1}^N \log d \sum _{n=1}^{N/d} \frac{\phi(n)}{\log (dn)},$$ converges or not when $N$ goes to infinity?
wongpin101's user avatar
4 votes
1 answer
336 views

Hejhal's algorithm and computational methods for non-classical Maass wave forms

Hejhal's algorithm [1] was a little gadget invented in the 90's for calculating the Hecke eigenvalues and Fourier coefficients of Maass wave forms. Later, Booker, Strombergsson, and Venkatesh (BSV) [2]...
Robert K's user avatar
  • 309
11 votes
1 answer
532 views

When adding a constant makes a multivariate polynomial reducible?

Given a multivariate polynomial $f(x_1,\dots,x_n)$ with integer coefficients, how to find an integer $m$ (if it exists) such that $f(x_1,\dots,x_n) + m$ factors into polynomials of smaller degrees? ...
Max Alekseyev's user avatar
1 vote
2 answers
321 views

Transformation of a bivariate polynomial into a homogeneous one

For a given a bivariate polynomial $P(x,y)$ with rational coefficients: Q1. How compute such (invertible) substitutions of its variables that would transform the polynomial into a homogeneous one? In ...
Max Alekseyev's user avatar
0 votes
2 answers
734 views

On reducible polynomials with positive coefficients, $1$ as constant coefficient and certain bounds on coefficients

Given $a \in \mathbb{Z}$ with $a > 1$. Let $g(x) \in \mathbb{Z}[x]$ be a polynomial with $g(a)=\pm 1$. Let $h(x) \in \mathbb{Z}[x]$ be a polynomial with $h(a)= p$, a prime. Let $g(x)$ and $h(x)$ ...
8 votes
1 answer
1k views

Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?

Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
Wolphram jonny's user avatar
2 votes
0 answers
300 views

Large numbers in small systems

Can we ever know the sum of the first $10^{10^{100}}$ digits of $\pi$? Can we calgulate the $n$th digit of $\pi$ when the Kolmogorov-complexity of $n$ is larger than the complexity of the calculating ...
user avatar
13 votes
3 answers
1k views

Is there a composite number that satisfies these conditions?

We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case $a+bi=3+...
wanglei's user avatar
  • 131
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 ...
4 votes
4 answers
761 views

Proving a least prime factor

Suppose that I find a small prime factor $p$ dividing a large number $n$ and I wish to prove that it is the least prime dividing $n$. There are two obvious approaches: either factor $n/p$, or divide $...
Charles's user avatar
  • 8,974
6 votes
1 answer
454 views

Solving equations in a subset of rational numbers

Let $S$ be a set of all positive rational numbers $x$ such that $2x^2 - 1$ is a square, excluding $x=1$. I am interested in computing as many as possible solutions in $S$ to either the following ...
Max Alekseyev's user avatar
1 vote
1 answer
210 views

Counting modular squares in an interval

For an integer $m$, let $S^m_{x_0,x_1} = \{ t | x_0 ≤ t ≤ x_1 $ and $t$ is a square modulo $m \}$. Let $S^m_x$ = $S^m_{0,x}$. Determining whether the sets $S^m_x$ are empty is easy (1 is always a ...
Stephan Wehner's user avatar
3 votes
2 answers
1k views

Integer partition and sum of squares

Hello, The question below might be well known, and using different words (I made these up, I'm not a number theorist or specialist in combinatorics) For all integers $n\geq 2$ denote by $\mathcal{P}...
Portland's user avatar
  • 2,752
4 votes
1 answer
363 views

Most orthogonal lattice basis

Let $n \in \mathbf{N}$ be a natural number and $v_1,\cdots,v_n$ a set of basis vectors in $\mathbb{R}^n$. How does one find the matrix $g \in \mathbf{GL}_n(\mathbb{Z})$ orthogonalizing these best ...
Tiffy's user avatar
  • 97
0 votes
1 answer
178 views

Efficiency in deriving differences of divisor pairs

I have a computational problem where I need to derive the differences in divisor pairs in as few cpu cycles as possible. In particular I am interested in divisors of numbers of the form $x^3+3*x^2*y+...
Kevin Acres's user avatar
5 votes
2 answers
815 views

12 descent scripts for pari/gp

I'm looking around for scripts to facilitate 12 descent on Mordell curves, preferably in Pari/gp. I understand that Magma implements this feature, but unfortunately this software isn't available to ...
Kevin Acres's user avatar
18 votes
2 answers
6k views

Efficient computation of integer representation as a sum of three squares

Recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the number of representations ...
Anton's user avatar
  • 1,573
11 votes
1 answer
360 views

Does this notion of pseudoprime relative to a matrix appear in the literature?

Let $M$ be a square matrix with integer entries. Then Fermat's little theorem for matrices holds: $$\text{tr}(M^p) \equiv \text{tr}(M) \bmod p.$$ This follows by an examination of the action of the ...
Qiaochu Yuan's user avatar
14 votes
2 answers
1k views

Saying things rapidly about integer factorisations

Let $N$ be a positive integer. Thanks to the Miller-Rabin test and the work of Agrawal, Kayal and Saxena, these days people have much much faster algorithms for testing whether $N$ is prime or ...
James Cranch's user avatar
  • 3,034
8 votes
1 answer
1k views

Recent Fast Multiplication Algorithms for Large Integers

The STOC 2008 paper "Fast Integer Multiplication using Modular Arithmetic" by De et al http://arxiv.org/abs/0801.1416 shows how to use $p$-adic numbers instead of $\mathbb C$ used in Furer's ...
Igor Markov's user avatar
2 votes
1 answer
199 views

Is there a security analysis of the GQ digital signature scheme?

I'm doing summer cryptography research and I am have been looking for a security analysis of the Guillou-Quisquater (GQ) digital signature scheme, but I have been unable to find one. Since this is not ...
Samuel Reid's user avatar
  • 1,401
8 votes
5 answers
4k views

Computational number theory

I am interested in learning computational number theory and doing some computer experiments. Which sort of number theory problems can be solved by using computers? For example, is it possible to ...
0 votes
2 answers
3k views

Fibonacci Numbers Modulo m [closed]

In the paper "Fibonacci Series Modulo m" by D.D. Wall (found here), there is a table in the Appendix listing values for the function $k(p)$. This function is defined as the period of the Fibonacci ...
Vincent Russo's user avatar
1 vote
0 answers
122 views

What is the largest computed summatory liouville interval ?

I am interested to know the largest computed summatory liouville interval, an implementation of which is detailed in Section 4.1 of [1]. The wikipedia page [2] for the function charts summatory ...
Rob's user avatar
  • 11
2 votes
0 answers
255 views

Efficient counting of Egyptian fractions with bounded denominators

I was amazed to discover that sequence http://oeis.org/A020473 in the OEIS has almost four hundred terms computed. I wonder how one can get that far? E.g., how one can compute A020473(100)? P.S. ...
Max Alekseyev's user avatar
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
  • 8,974
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
  • 8,974
11 votes
2 answers
752 views

Interesting result on the Euler-Maschroni constant - what is the background?

Today I entered the following expression in maple: $$a_i = H_{10^i} - ln(10^i) - \gamma$$ Here $H_j$ equals $\sum_{k=1}^{j} 1/k$ and $\gamma$ is the Euler-Mascheroni constant. When I computed $a_n$ ...
tobias's user avatar
  • 377
6 votes
2 answers
2k views

Computing the fixed field of an automorphism of a function field

Let say we have a function field $k(x,y)$ defined by $f(x,y)$ over $k$, with $\sigma \in Aut(k(x,y)/k)$ and. Suppose, I'm not that out of luck, so that either of $\prod \sigma^i(x)$ or $\sum \sigma^i(...
Syed's user avatar
  • 601
2 votes
0 answers
362 views

Rational integer solutions of a linear Diophantine equation of cyclotomic integers

I am working with lattices in $\mathbb{C}$, and I want to know whether a certain vector is an element of the lattice. In particular, suppose my lattice vectors are $a$ and $b$ and I want to know ...
M.J. Loquias's user avatar
9 votes
2 answers
761 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
39 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}}$.
Vladimir Reshetnikov's user avatar
1 vote
0 answers
428 views

Witt rings and prime number generator?

Let $p$ be a fixed prime number. We define the ring of Witt vectors $W(R)$ for any commutative ring $R$ as follows: For every ring morphism $R \rightarrow R'$ the induced morphism $W(R) \rightarrow ...
tobias's user avatar
  • 377
3 votes
1 answer
300 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
1 vote
0 answers
204 views

Which rational subfields are corresponding to the two dimensional subspaces of holomorphic differentials

I implemented the algorithm that Felipe Voloch's suggested in his reply to the question: Subfields of a function field the algorithm is here: Subfields of a function field I considered the ...
Syed's user avatar
  • 601
8 votes
3 answers
1k views

Effective detection of CM modular forms

Say $f$ is a newform of weight $k$ and level $\Gamma_1(N)$. $f$ is called CM if, for example, there is an imaginary quadratic field $K$ such that for all $p\nmid N$ which are inert in $K$, the $p$th ...
Rob Harron's user avatar
  • 4,777
4 votes
0 answers
245 views

Algorithm/denominators of elements of a rational affine space

I hope it's not a trivial question... Suppose I have a finite dimensional vector space $V$ over $\mathbb{Q}$ with a distinguished basis (in my case it's the $k$th graded piece of the free associative ...
Adrien's user avatar
  • 8,234
4 votes
0 answers
159 views

Range of the least witness function

Let W(n) be a function from the positive odd composite numbers to the least positive b such that n is not a b-strong pseudoprime. W(n) exists for all numbers in its domain and its range is unbounded. ...
Charles's user avatar
  • 8,974
5 votes
0 answers
285 views

Lower bound for p-adic distance between roots

Let $f$ be a formal power series with coefficients in the ring of integers of a finite extension of ${\mathbb Q}_p$. Is there a simple algorithm to compute a positive lower bound for $|\alpha - \beta|...
Jesse Elliott's user avatar
1 vote
0 answers
107 views

Why do subspaces of the space of Global holomorphic differentials of a function field correspond to its subfields

I'm asking this question as a follow up to the Felipe Voloch's answer to this question: Subfields of a function field which you can read it here: Subfields of a function field (I just didn't have ...
Syed's user avatar
  • 601
1 vote
1 answer
317 views

Number of biquadrates mod n

Is there an explicit formula for the number of fourth powers mod n? Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...
Charles's user avatar
  • 8,974
8 votes
1 answer
715 views

Finding colinear points in F_q^n

Forgive me if this is well known, it's not really my field, but it's a problem I've run across and thought about a bit. Let $\mathbb{F}_q$ be a finite field with $q$ elements, let $n\ge2$, and let $A,...
Joe Silverman's user avatar

1
5 6 7
8
9