# Tagged Questions

The tag has no usage guidance.

107 views

### Structured factoring

Is it easier to factor $$(ax + b) (ay+ c)=M$$ where $a,b,c\in\Bbb N$ are known where $b$ and $c$ are similar in size and $a$ is approximately $b^{2/3}$ and unknowns $x,y\in\Bbb N$ and are ...
66 views

### Algorithm for checking linear independence of algebraic numbers

Is there any if and only if condition for checking $Q$-linear independence of given a set of numbers say $\alpha_i$ ? More precisely how to check linear independence of given $n$ algebraic numbers (...
111 views

### Primitive element for a number field, and ramification

Let $K=\mathbb Q(\theta)$ be a number field with integral primitive element $\theta$, and let $f(x)$ be the minimal polynomial of $\theta$. Let $p$ be a rational prime. It's well known that if $p$ ...
105 views

### More generalized RSA construction

Is there a way to construct RSA type cryptosystem over general number rings? Can Number Field Sieve technique be applied here?
58 views

### Algorithm to generate random polynomials which has root in Q(a) where a is another algebraic number

Suppose you are given an algebraic number $\alpha$ . It is represented by $(p(x),(a,b),r)$ where $p(x)$ is its minimal polynomial. $a+ ib$ is an approximation of $\alpha$ such that there is no other ...
166 views

### Computing coefficients for the slash operator of a modular form

Suppose $f$ is a classical modular form of weight $r$ for a (congruence) group $\Gamma$. Let $\gamma$ be any matrix in $\operatorname{SL}_2(\mathbb{Z})$. Then the slash operator $|_\gamma$ is usually ...
92 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 ...
154 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 ...
230 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 ...
354 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 ...
268 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 ...
495 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}}$$ ...
500 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 ...
135 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 ...
203 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$ ...
126 views

228 views

### A three variable linear diophantine promise problem

Given $a,b,c,s\in\Bbb N$ such that $(a,b,c)=1$ with promise that we have at most one triple $x,y,z\in\Bbb N$ such that $ax+by+cz=s$, what is a good algorithm that runs in $O(\log(abcs))$ time to find ...
195 views

### On Pell's equation

A post was made (Reduction from factoring to solving Pell equation) seeking clarification to solving $$x^2-Dy^2=1$$ to factoring when $D>0$. An answer was posted stating that to factor $N$, it ...
80 views

### Runge-Kutta convergence [closed]

I am facing a problem solving a ODE with a Runge-Kutta 4th order method: The expression in order to solve is : $$Ay^{''}+By^{'}+Cy= Cu$$ y =OUTPUT \end{...
57 views

### lattice basis reduction of the orbit of a rational vector on the torus

LEt $v=(p_1/q,...,p_n/q)$ be a vector of the torus $\mathbb{T}^n$, such that for any $i$, $p_i$ and $q$ are relatively prime. Let $L= \{ kv \mod \mathbb{T}^n , k=0,...,q-1 \}$. What is the lattice ...
313 views

560 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$...
121 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 ...
105 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 ...
240 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 $\Omega_\pm$,...
268 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 ...
179 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 $P$...
240 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$. ...
165 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 $A$...
252 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 ...
175 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})$. ...
225 views

### Rings of algebraic integers as quotients of polynomial rings

The ring of integers $\mathcal{O}_K$ of a number field $K$ is always isomorphic to some ring of the form $\mathbb{Z}[x_1, ..., x_r]/\mathfrak{p}$, where $\mathfrak{p} \subset \mathbb{Z}[x_1, ..., x_r]$...
260 views

### How to define the input of computable function or Turing machine over real numbers

Computation or computability over $\mathbb{N}$ can be extended to computation or computability over $\mathbb{R}$ or even computation or computability over $\mathbb{C}$.The following is a formal ...
### 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 ...