NumberWorld

Jailbreaking ChatGPT’s Filters: How Far Can Clever Prompting Go? Modern AI systems have sophisticated guardrails designed to block copyrighted material, harmful content, and sensitive data. But how strong are these defenses really? For years I’ve been fascinated by where these filters actually operate — on the input, during reasoning, or on the final output? This isn’t about breaking laws. It’s about understanding the limits of current alignment techniques. Can you trick the AI to output content that should actually behind some filter wall? By a happy coincidence, since i am a big fan of Quanta Magazine, i stumbled over a nice related article for a few weeks [1] which influence this post.

In this article, we demonstrate a subtle but devastating backdoor in finite-field Diffie–Hellman. By computing public keys modulo $p^2$ instead of $p$ while restricting the secret exponent to $x \leq p-1$, the discrete logarithm becomes efficiently recoverable using Fermat quotients. We show the full derivation and provide a working Sage implementation. Backdoors are always bad — but they are catastrophic when they are embedded in a fundamental primitive like Diffie–Hellman key exchange. If your browser shows a green lock, you assume your connection is secure. But what if the implementation of Diffie–Hellman contains a tiny change that looks harmless in code review — and yet allows an attacker to recover the private exponent in milliseconds? In this post I’ll show a nasty little backdoor that requires only a tiny modification: using a modulus of $p^2$ instead of $p$, while keeping the secret exponent bounded by $p$ This ...

F actoring integers is a well studied topic in mathematics and computer science. The number of approaches to this problem numerous. There are even some graph related approaches to this problem. One particular, but not very efficient way, which i also covered in a previous blog post , is to convert an integer to a 3-USAT formula and find the unique satisfying assignment. I never heard of an approach that converts the integer factorization problem to a perfect matching problem. Main Goal.  What we want to accomplish with our approach is to build a planar graph $\mathcal{G}$ that reassembles an $n$-bit multiplier.  $\mathcal{G}$ should be build in a way that it has  exactly one perfect matching (or some derived graph has a perfect matching) and this perfect matching reveals the factorization of the given product $pq$. O ne way to realize multiplication of two $n$-bit numbers $p$ and $q$ in hardware is to build a network of cascading $n^2$ adder gadgets. Such a constructio...

This blog post is about De Bruijn sequences and its relationship to cryptography. We focus here on De Bruijn sequences over the alphabet $A=\{0,1\}$. Definition [De Bruijn sequence (binary)] .   A binary string of length $2^n$ is called a De Bruijn sequence of order $n$ if each possible $n$-bit string occurs exactly once (incl. wrap-around) as a substring.  Picture 1 - DeBruijn graph for n=3 De Bruijn sequences are the shortest possible bitstring that contains all possible $n$-bit substrings. For each $n$ there are $$\frac{2^{2^{n-1}}}{2^n}$$ possible De Bruijn sequences. For example, a De Bruijn sequence of order $n=3$ is $$00011101$$ and of order $n=4$ is $$0000101100111101$$ There are several ways to create De Bruijn sequences. One way is walk along an  Hamiltonian Cycle in the corresponding De Bruijn graph (see Picture 1) . A De Bruijn graph is a directed graph of degree $2$ which has $2^n$ vertices. There is an edge from vertex $i$ to the two vertices $$(2i\;...

🔲  This post is related to a paper of mine (Title:  On the construction of graphs with a planar bipartite double cover from boolean formulas and its  application to counting satisfying solutions )  that will get published later this year in the Journal of Theoretical Computer Science . It is related to [ this ] blog post which i wrote already four years ago and settles some of its questions. In a short overview, the paper adresses the following action chain: Assume you have a boolean CNF formula   $\Phi$ You build the incidence graph $\mathcal{I}$ of $\Phi$ using some techniques from the literature, e.g., each clause is represented by a node and also each variable is represented by a node. Then there is an edge between a clause-node and a variable-node if the variable occurs in that clause in $\Phi$. You replace each node in $\mathcal{I}$ with a gadget, i.e., a small graph that has certain properties, which only have edge weights from 0 and 1. The proper...

One of my favorite object in graph theory are Matchings , especially Perfect Matchings (PMs). Let me restate the definition of a PM briefly: Definition (Perfect Matching) Given a graph $\mathcal{G} = (E,V)$, then a Perfect Matching $M$ is a set of pair-wise non-adjacent edges from $E$, such that every vertex in $V$ is touched by one edge in $M$. Here is a little example for a two PMs in a graph: Figure 1 - Top: The original graph $\mathcal{G}$; Below: The red lines indicate two example perfect matchings in $\mathcal{G}$ This post list some of the properties of PMs regarding finding and counting them in different graphs types. During writing this posts, i found that a similar listing can also be red in [6].

Blogposts are good place to write things up, because they do not magically disappear as most of the handwritten notes on my desktop. I was creating a list of different types of CNF formulas to mark which restrictions makes counting solutions or deciding satisfiability polynomial computable. Such an overview is certainly not new but i did not find a sufficiently complete list. So i tried to come up with such a list by myself and thought it could be of some interest for you. The restrictions i was aiming at have the following abbreviations: $\text{Ex3SAT}$ : Each clause has exact $3$ variables $\text{Pl}$ : The incidence graph of a formula $\Phi$ is planar $\text{Tree}$ : The incidence graph of a formula $\Phi$ is a tree $\text{Mon}$ : Monotone, i.e., each variable occurs only in positive form $\text{Rtw}$ : ReadTwice, i.e., each variable occurs at most twice $\text{x-in-N}$ : Exactly $x$ variables out of $N$ must be true in each clause. So $\text{1-in-3-3CNF}$ also forces that e...

D uring the last months i spent some of my free time to read several books and interesting articles. E.g. " The Golden Ticket : P, NP, and the Search for the Impossible " by Lance Fortnow or Scott Aaronson's " Quantum Computing since Democritus ". In the former the author describes in one chapter how the world would look like if P = NP. He is by no way the first who thinks and writes about this, but he did it in a very extensive and pictured way. It was intriguing to read what kind of things would become possible if this rather mathematical problem would be solved. The world can be described at best with " Everything that we can quickly recognize as being a good solution for a problem, we can find quickly " But more on this later. Of course, an existential proof would not change much, besides the receipt of one million dollars from the clay institute. If you just prove that there has to be an algorithm that could solve the traveling salesmann probl...

Creating hard instances of computational problems can be easy (e.g., Factoring), cumbersome (e.g, SAT) or hard (e.g. Graph Isomorphism). So using a problem that allows to create instances in an easy way and then transform it into an instance of another problem is often a good idea, as long as the transformation is feasible. In this post i want to show how factoring can be reduced to a boolean formula $\varphi$ such that finding a satisfying assignment of $\varphi$ reveals a factor of the original integer. So if you think you found an algorithm that solves SAT in polynomial time, you should use this approach to convert a 2048-bit RSA instance to a SAT instance and test how it behaves :) The approach is analogous to the approach of ToughSAT . For a high level overview, the algorithm works like this: Input: $N = pq$, with unknown primes $p$ and $q$. $n \leftarrow$ bitlength(N) Take $2n$ variables for the binary representation of $p$ and $q$ and write: \begin{align*} x_{n-1}x_{n-2}...

This post shows an introduction to Holographic Algorithms (HA). From my point of view, Holographic Algorithms were motivated by analogies to quantum computing and to overcome some of the obstacles that occur when one follows Leslie Valiant's original approach using the permanent and cyclic covers to count satisfying solutions for boolean formulas. Again, the basic ingredient for HAs is the efficiently computable FKT-algorithm, which works because of the grateful fact that we are able to compute the determinant in polynomial time. The literature of Holographic Algorithms (which are a generalization of CSP-Problems) is huge and is dominated by works of Valiant, Cai and Lu, see e.g. [1,2,3]. The central theorem is the Holant Theorem , which proofs the equality of the number of perfect matchings of a graph $\mathcal{G}$ and the value of the Holant Function. The Holant Function is applied to a matchgrid , that is a graph composed of certain subgraphs (called matchgates), such that ...

Some say Computational Complexity is all about the $1$-million worth question $$\mathsf{P} \overset{?}{=} \mathsf{NP}$$ Of course, this is far from being correct. There are many more complexity classes and many more models of computation. Technically, the two classes $\mathsf{P}$ and $\mathsf{NP}$ are not special. But they are of special interest, since they pose a barrier between what perhaps can be computed on our classical computers in a feasible amount of time and those problems that in many cases would require an exponential amount of time. Or, spoken in a more simple way, they show up the barrier between what can be computed and what can not be computed due resource constraints. However, there are some problems that have some weird special cases, which seem to be missed accidentally by the claws of the $\mathsf{NP}$ monster and fell into the lower class of $\mathsf{P}$. Both examples are actual based on the beautiful work of Leslie Valiant who showed how to connect the probl...

This post is dedicated to give you an implementation (in SAGE) of the FKT-algorithm . I coded this while spending some time on the ideas i explained in this blog post . I searched several hours to find an existing implementation without success. Since it took me a while to code this on my own, i think it is worth to present it, therewith other can use it in their own work. It works well, but if you find an error, please leave a note. The FKT-algorithm can be used to count the number of perfect matchings in a planar graph. And a graph is planar if and only if it does not have K$_5$ or K$_{3,3}$ as a minor . A paper that will be presented at the CCC conference this year is called : Counting the Number of Perfect Matchings in $K_5$-free Graphs [ in polynomial time ] Simon Straub (Ulm University), Thomas Thierauf (Aalen University), Fabian Wagner (Ulm University) I did not manage to read it yet, but i am curious to see, how they circumvent the K$_{3,3}$ minor problem. ##########...

The graph isomorphism ($\mathsf{GI}$) problem is one of the few known problems in computational complexity that are in the complexity class $\mathsf{NP}$, but neither known to be in $\mathsf{P}$ nor in $\mathsf{NP}$-complete. So it is a very good candidate for a so called $\mathsf{NP}$-intermediate problem. Another well known candidate is factorization. For many types of graphs the $\mathsf{GI}$ problem could be solved efficiently, i.e., using only poly($n$) many resources, whereof $n$ is the number of vertices in the graph. However, one is able to generate hard instances where all the algorithms fail and an exponential amount of resources is needed in order to solve the problem. But finding such hard instances is not easy. In particular for random graphs, the isomorphism problem is almost always easy. So the average complexity of $\mathsf{GI}$ is low, but the worst case complexity is hard. Definition [Graph Isomorphism] Two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$ are isomorphic if...

Computational Complexity is a really fascinating area of research. One particular surprising fact that i learned years ago is the discrepancy between the computational effort to compute the determinant of a matrix and the permanent of a matrix. The determinant is defined as: \begin{equation} \text{det}(\text{A}) = \sum_{\sigma \in S_n}\text{sign}(\sigma)\prod^n_{i=1}a_{i,\sigma_i} \end{equation} and the permanent is \begin{equation} \text{perm}(\text{A}) = \sum_{\sigma \in S_n}\prod^n_{i=1}a_{i,\sigma_i} \end{equation} The difference in notation is minimal. The determinant considers the sign of the permutations $\sigma$ whereof the permanent does not. This little difference is responsible for the huge gap between the necessary resources that are needed in order to compute the actual value of these functions. The determinant can be evaluated in time that is polynomial in the dimension $n$, whereof the permanent is only computable in time that is exponential in $n$, e.g., using th...

To show that quantum computers are indeed able to solve some problems more efficiently than classical computers, one of the first problems that were published was Simon's problem. Definition [Simon's problem] Let $f:\{0,1\}^n \rightarrow \{0,1\}^n$ with the property that for $x,y \in \{0,1\}^n$ it is $f(x) = f(y)$ if and only if $x = y \oplus a$, for some fix value $a \in \{0,1\}^n$. Given $f$, the task is to find $a$. As usual the $\oplus$ is the bitwise XOR-function. On a classical computer, Simon's problem can only be solved in time that is exponential in $n$, whereof on a QC already $\mathcal{O}(n)$ queries are enough. Simon's problem can also be seen as some kind of period finding problem. Assume you have a function $f$ and for $f$ it holds that: \begin{align} f(1) &= e_1 \\ f(2) &= e_2 \\ ... &\\ f(a-1) &= e_{a-1}\\ f(a) &= e_a = 1\\ f(a+1) &= f(1) = e_1\\ f(a+2) &= f(2) = e_2 \\  ... & \end{align} A non-triv...

Sorting integers and the corresponding algorithms is one of the first basic topics one learns in computer science. Bubble-Sort, Insertion-Sort, Merge-Sort, Quick-Sort, Radix-Sort and even many more are discussed during the first classes. For a general purpose sorting algorithm, that is one that is based on comparison operations, it is known that one can not do better than $\mathcal{O}(n\log n)$.  Radix-Sort for example, which is not a general purpose algorithm, since it works only for integers, has a running time for $k$-digit integers of $\mathcal{O}(kn)$. The sorting algorithm which i want to discuss today is Gravity-Sort  (Although Wikipedia calls it Bead-Sort .) It is based on a funny little idea to let gravity make the work for you. It has a theoretical runtime (assuming gravity is for free) of $\mathcal{O}(1)$. Implementing this on a normal pc would actually destroy this runtime because the gravity has to be programmed somehow.

▇ In this post I will talk about one of the most famous pieces of code optimisation that can be written in a single line of code. It can be found in the source code of the first-person shooter Quake 3, and is probably the reason why it got so much public attention. It involves the calculation of the inverse square root of a floating point number. See also the bibliography of the Wikipedia article Fast inverse square root for more information. Here is the code: 1: float InvSqrt ( float x) { 2:   float xhalf = 0.5f*x; 3:   long i = *( long *)&x; 4:   i = 0x5F83759DF - (i>>1);  //initial guess of inv-sqr 5:   x = *( float *)&i; 6:   x = x*(1.5f-xhalf*x*x);    //one step of newton iteration 7:   return x; 8: } A single execution of this InvSqrt -Function yields a very good approximation to the inverse square root. It is said, that it is $4$-times faster than the native division...