Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.

A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. We consider the direct product of complete graphs Km × Kn. It is known that if at least one of the numbers m or n is even, then Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1, except when m = n = 2. We prove that the graph Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1 when both m and n are odd numbers, ensuring in this way that all graphs Km × Kn have total chromatic number equal to ∆ (Km × Kn) + 1, except when m = n = 2.

Important papers have appeared recently on the problem of indexing binary strings for jumbled pattern matching, and further lowering the time bounds in terms of the input size would now be a breakthrough with broad implications. We can still make progress on the problem, however, by considering other natural parameters. Badkobeh et al. (IPL, 2013) and Amir et al. (TCS, 2016) gave algorithms that index a binary string in O(n + r^2 log r) time, where n is the length and r is the number of runs, and Giaquinta and Grabowski (IPL, 2013) gave one that runs in O(n + r^2) time. In this paper we propose a new and very simple algorithm that also runs in O(n + r^2) time and can be extended either so that the index returns the position of a match (if there is one), or so that the algorithm uses only O(n) bits of space instead of O(n) words.

Sorting by transpositions is a challenging classic problem proposed in genome rearrangement and recently settled as NP-hard. Although the proven hard to sort $3$-permutations are close to the identity, the historical approach has been to study distant permutations, possible candidates to be diametral. The transposition diameter is a related challenging problem, known only for $n \leq 15$. We advance the study of both transposition distance and diameter by considering lonely permutations and the union operation. We present tighter bounds for the distance of lonely $3$-permutations, $u_{n,n-1}$, $u_{n,\frac{n}{2}}$, $u_{n,3}$, and $u_{n,4}$. We set the current lower bound for the transposition diameter back to $\big\lfloor\frac{n+1}{2}\big\rfloor+1$ and propose an alternative union of lonely permutations contributing to the approach used so far in the literature.

H. Eriksson et al. made a breakthrough to the problem of sorting by transpositions by proposing a quotient structure named toric graph, which allowed the reduction of the search space, establishing the transposition diameter $D_t(n)=\lfloor\frac{n+1}{2}\rfloor+1$, for the cases $n=13$ and $n=15$, and invalidating a conjecture by J. Meidanis, M. E. M. T. Walter, and Z. Dias that the transposition diameter would be equal to the transposition distance of the reverse permutation $\lfloor n/2\rfloor+1$. I. Elias and T. Hartman extended the lower bound $D_t(n)\geq\lfloor\frac{n+1}{2}\rfloor+1$, to all odd values of n, $n\geq13$. The value $n=15$ is the largest for which $D_t(n)$ is known. The goal of the present paper is to further study the toric graph, focusing on the case when $n+1$ is prime, providing positive evidence that J. Meidanis, M. E. M. T. Walter, and Z. Dias's conjecture is still valid when n is even. We show that, when $n+1$ is prime, the properties of the reverse permutation are shared by permutations that fall into unitary toric classes; we prove that their reality and desire diagrams have just one cycle, consequently proving that those permutations are separated by at least $n/2$ transpositions among themselves, and we show that there are at least two permutations whose transposition distance is $n/2$ and two permutations, other than the reverse, whose distance is at least $n/2+1$, with respect to the identity.