The computational-number-theo tag has no wiki summary.
1
vote
1answer
195 views
+50
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, ...
0
votes
0answers
156 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 ...
0
votes
1answer
175 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 ...
1
vote
2answers
109 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 ...
5
votes
3answers
284 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?
1
vote
0answers
241 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 ...
0
votes
0answers
74 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 ...
3
votes
2answers
215 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?
0
votes
0answers
103 views
3SAT to Quadratic Diophantine Equation?
I've been reading Mander's & Adleman's paper on "NP-Complete decision problems for binary quadratics" (https://www.sciencedirect.com/science/article/pii/0022000078900442?np=y). Could someone help ...
2
votes
1answer
143 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) ...
0
votes
0answers
57 views
Lower bound on number of solutions to diophantine equations with all but one linear constraint
Hi,
I want to ask a simple question in diophantine systems. I have tried to search under different headings, but was unable to find a suitable answer to my question.
I have a set of $m$ linear ...
7
votes
0answers
203 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?
...
1
vote
2answers
160 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 ...
0
votes
2answers
404 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)$ ...
7
votes
1answer
578 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, ...
2
votes
0answers
242 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 ...
11
votes
4answers
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 ...
5
votes
3answers
410 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 ...
2
votes
3answers
306 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 ...
5
votes
1answer
274 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 ...
1
vote
1answer
151 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 ...
2
votes
2answers
400 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 ...
4
votes
1answer
192 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 ...
0
votes
1answer
136 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 ...
5
votes
2answers
421 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 ...
7
votes
1answer
218 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 ...
10
votes
2answers
548 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 ...
7
votes
0answers
368 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 ...
0
votes
0answers
74 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 ...
0
votes
0answers
99 views
Pre-requisites for Computational Mathematics [closed]
I have been searching the net for a few days as to what all courses i must have done to make sense of the field of Computational Mathematics.
I came up with these:
1.) Discrete Mathematics and Data ...
3
votes
3answers
450 views
Computational number theory
Hello everybody!
I am interested in learning computational number theory and doing some computational experiments by computer!
I was wondering which sort of number theory problems can be solved by ...
0
votes
2answers
544 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 ...
0
votes
0answers
88 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 ...
1
vote
0answers
137 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. ...
8
votes
3answers
696 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. ...
13
votes
1answer
715 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 ...
10
votes
2answers
625 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$ ...
4
votes
2answers
757 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 ...
5
votes
2answers
371 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 ...
15
votes
1answer
1k 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}}$.
1
vote
0answers
299 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 ...
4
votes
1answer
273 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 ...
1
vote
0answers
178 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 ...
6
votes
3answers
667 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 ...
3
votes
0answers
120 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. ...
4
votes
0answers
192 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 - ...
1
vote
0answers
86 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 ...
0
votes
0answers
168 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 ...
7
votes
1answer
523 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 ...
2
votes
0answers
230 views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
