# Tagged Questions

The tag has no usage guidance.

86 views

### parametrizing a conic in $F_p$ [closed]

Let $F_p$ be a finite field and $p\equiv 3 \pmod 4$, and $a,c$ are non-square elements in $F_p$. I want to parametrize the conic: $$cy^2=-3x^2-2ax-16a$$ ($-1$ and $3$ are non-squares in this field ...
40 views

### Complexity of $\mathsf{gcd}(a,b)\bmod N$

Given $a,b\in\Bbb N$ where each $a,b$ is $n$-bits, we can compute $\mathsf{gcd}(a,b)$ in $cn^{1+\epsilon}$ bit operations for some fixed $c\geq1$. My query is given $N,a,b$ where $a,b$ is $n$-bits ...
207 views

### Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...
347 views

### On the mixed sum of three k-th powers

Let the set $S_k=\{\pm x^k \pm y^k \pm z^k \ \vert \ x,y,z \in \mathbb{Z} \}$. Note that the signs are independently positive or negative. First of all $S_2 = \mathbb{Z}$ because (see the answers ...
260 views

### The limit of the following product? What is the closed form of the value?

Assume that $P_n$ is the $n$'th prime: Please help me solve the following $$\lim_{k\to\infty} {k}\prod_{n=1}^k \frac{P_{2n-1}}{P_{2n}}$$ I am not really sure quite where to start here as I am ...
466 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}}$$ ...
484 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 ...
123 views

### Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent? Is there any group for which we suspect them to be different? Could there be a finite ...
197 views

### Avoiding Chinese Remainder Theorem

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
120 views

### On factorization algorithms for $\mathcal{O}[x]$

We know that $\mathsf{LLL}$ algorithm provides factorization procedure that runs in poly time for polynomials in $\Bbb Z[x]$ that are primitive. What other rings $\mathcal{O}$ can we use instead of ...
80 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$ ...
45 views

### Finding spanning vector sets

Let $V$ be the set of all vectors over the non-negative integers. For any two subsets $S$ and $T$ of $V$, define $S + T$ to include: All vectors in $S$ All vectors in $T$ All vectors that can be ...
512 views

### On bounds for idoneal integer

What is the best known lower bound and upper bound known for such a number if it exists and have there been any attempts (computational including) to eliminate the existence of such a number in known ...
195 views

Assume that following inequality holds $$\mathsf{w,x,y,z<AB,AC,AD,BC,BD,CD<ABC,ABD,ACD,BCD<wx,wy,wz,xy,xz,yz}$$ with $$\mathsf{gcd(A,B)=gcd(A,C)=gcd(A,D)=gcd(B,C)=gcd(B,D)=gcd(C,D)=1}$$ ...
223 views

506 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 ...
117 views

### algorithm to find a new point of small height in a number field extension

By the height of an algebraic number $\alpha$, I mean the absolute, logarithmic (additive) Weil height $h(\alpha)$; e.g. $h(2^{1/n}) = (\log 2)/n.$ If $K$ is a number field, let $\delta(K)$ denote ...
103 views

### Comparing the size of two sums

Let $q$ be a prime power and $\mathbb{F}_q$ be the field of $q$ elements. Let $\mathbb{F}_q[t]$ be the polynomial ring over $\mathbb{F}_q$. I am working on a research project, where I bounded a ...
234 views

### Error term for prime harmonic

What is known about the asymptotic behavior of $$f(x)=\sum_{p\le x}\frac1p-\log\log x-B_1?$$ Of course by Mertens we know that $f(x)=o(1),$ but has more been proved (in terms of $O$ or ...
253 views

### Residues and values of Riemann Zeta function at some points

I need the following computational results for proving something. Let $1/2 + i\gamma_0$, be the first nontrivial zero of Riemann zeta function, $\zeta(s)$, i.e. $\gamma_0\sim 14.134...$. 1) what is ...
176 views

### Monte Carlo variant of Hilbert's Tenth Problem

Let $k \in \mathbb{N}$. Given an algorithm $\mathcal{A}$ which takes as argument a polynomial $P \in \mathbb{Z}[x_1,\dots,x_k]$ and either returns true or false, we say that $\mathcal{A}$ works for ...
235 views

### On the ratio of Gilbreath sequences

Definitions: let $n \in \mathbb{N}_{>0} \cup \{ \infty \}$ and let $E_n$ be the set of sequences $(d_i)_{i=1}^n$ such that $d_1=1$, $d_i$ is an even integer (for $i > 1$) and $0<d_i \le i$. ...
159 views

### What is the ring $A_{\Gamma}$ in the Cohen-Lenstra Heuristics?

I understand the work in Cohen and Lenstra's paper that leads up to the heuristics themselves, where they count weighted averages of functions defined over isomorphism classes of $A$-modules, where ...
233 views

### Computing all “suboptimal” rational approximations to $\pi/2$

I have an irrational number $\alpha$ ($\alpha=\frac\pi2$), and I would like to determine all integers $n\in[1,N]$ ($N=10^{16}$) that satisfy $$n \epsilon(n)^2 \leq \tau$$ where $\tau$ is a known ...
174 views

### Fourier expansions of newforms at width-1 cusps

Let $f_E$ be the newform attached to the Elliptic Curve $E$ with cremona label $\textbf{100a1}$ and let $\alpha = \left[\begin{matrix} 1&0 \\ 10&1 \end{matrix}\right] \in SL_2(\mathbb{Z})$. ...
200 views

984 views

Could anyone try to prove that the below conjectured formula is valid for relating $\pi$ with ALL of its convergents - those, which are described in OEIS via A002485(n)/A002486(n) ? $$(-1)^n\cdot(\pi ... 1answer 110 views ### Growth of the truncation of the integral multiples of an irrational number Let [a] denote the integral part of a real number a. Let a be an irrational number and b a real number greater than 1. Consider the sequence (b^n(na-[na])) with n running on the ... 2answers 327 views ### Computational complexity of solution of Pell equation and more What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity? And more,could ... 1answer 106 views ### Size of approximate solution of an integer relation Let X_1, ..., X_n be a list of real numbers. Consider an integer relation equation A_1 X_1 + \ldots + A_n X_n = 0 where A_1, ..., A_n are unknown integers. Suppose somehow we are not so ... 1answer 209 views ### Calculating (n ^ fibonacci(k)) MOD m for a large value of k The value of k can be very large indeed (up to 10^{12}). Is there an efficient way to calculate the output? Edit : 'm' is a prime number. 1answer 275 views ### Number Field Sieve for factorization with non-monic non-linear polynomial. Can't understand calculating ideal valuations There is a paper "Factoring integers with the number field sieve" (download it here, for example). I can't understand how they reason the correctness of computing ideal valuations in the case of ... 0answers 86 views ### Is there any track for proving D=NP, besides showing that D has polynomial-bounded universal quantifiers? Background By the MRDP theorem, every for every recursively enumerable set S, there exists a Diophantine polynomial p such that$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
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 ...