# Questions tagged [computational-number-theory]

Computational Number Theory is for explicit calculations or algorithms involving anything of interest to number theorists.

281 questions
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
86 views

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 ...
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$ ...
1k views

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 ...
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 ...
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 ...
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 ...
221 views

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....
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 ...
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 ...
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 ...
205 views

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 ...
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 \... 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... 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 ... 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 ... 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/...
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 ...