IV⇆PID

A fast, open-source IV⇆PID calculator for 3rd and 4th gen Pokémon

(versión del README en español aquí)

What is this?

The Random Number Generator for third and fourth generation Pokémon games is a 32-bit linear congruential generator that yields 16-bit numbers (from the high 16 bits of its state). This means that if you knew two consecutive numbers from the RNG, then you would know the (most of the time) only candidate to be the next number. This is almost always useless as you cannot easily get the exact number from the RNG, but it means that the Individual Values for a given Pokémon are tightly linked to its PID, as the PID is always the concatenation of two consecutive RNG calls and the IVs are obtained after the PID.

This link can be seen as a serious restriction on the possible Pokémon. For example, it is impossible to find a wild Pokémon with Bold nature and 31 IVs in every stat in any of these games. Some legality checkers for 3rd and 4th gen Pokémon games rely on this link and check if the IVs and PID of a Pokémon fit this link: if they do not (and the Pokémon was caught, not hatched from an egg or received as a gift), the Pokémon is obviously modified.

This tool can be used to get all possible IV-PID combinations from a PID or a set of IVs. You can also filter the search by nature, ability or shininess (which depend on the PID) and by Hidden Power type and base power (these ones depend on the IVs). The tool applies the theory developed in this Smogon article to do that, and relies on the reverse RNG sequence to get the PID from given IVs quickly.

There is another tool that does something like this: SCV's PID/IV Generator. That one gives you less options to filter the results, may give out some wrong IV-PID links (because it assumed a method that has been later shown to be wrong) and is outperformed by this tool at the task of finding PIDs for a shiny Pokémon which IVs are at least a given set.

How does it accomplish that?

The PID is generated by concatenation of two consecutive RNG calls. The first call will make the low 16 bits, and the second call will decide the high ones. Then the IVs will be chosen using two other RNG numbers (the lower 15 bits of the first number will yield the HP, Attack and Defense IVs and the lower 15 bits of the second one are responsible for the other IVs).

In GBA games, the RNG might take a one step jump between two of these numbers. The position that has been discarded sets the method. For example, the method A-B-C-E means that the fourth number (D) has been ignored and it was the fifth one (E) which has decided the Special Attack, Special Defense and Speed IVs. A-B-C-E and A-B-D-E might be chosen for wild Pokémon that you meet by walking, surfing or fishing (A-B-D-E seems to be the most common method for these ones), whereas A-B-C-D can be chosen for all wild Pokémon. Some people assert that in very rare cases some other methods are used for wild Pokémon. The method is always A-B-C-D for wild Pokémon in NDS games, that is, no number is discarded.

PID to IV

The high 16 bits of the RNG state right after the first call to the RNG are known: they are the low 16 bits of the PID. Then all the 65536 possible RNG states are explored to check if the next number matches the high bits of the PID. Every time it does, the IV distribution is shown. If GBA methods are allowed, one IV distribution for each method is shown.

IV to PID

This time we know 15 bits of the RNG state after the last number is obtained (the 16 high bits but the highest one) as they made the last IVs. The reverse RNG sequence is explored: all the 2·65536 possible states are checked to test if they match the wanted IVs for HP, Attack and Defense. If so, then the PID is obtained and shown.

The user can ask for more conditions: a nature, a fixed ability slot, a Hidden Power or shininess for a Trainer ID and a Trainer Secret ID. The set of required IVs can be chosen to be the exact IVs or a minimum for each stat (for this one, all the values for Special Attack, Special Defense and Speed IVs that are greater than the read from the user will be explored).

How have you found the reverse RNG sequence?

The author of that Smogon article proudly states here that he and another Smogon user had discovered the reverse RNG sequence independently, thus anyone who applies the reverse RNG sequence should give credit to one of them (that sounds as if Leibniz had stated that anyone who uses calculus should give credit to him or to Newton, lol). But anyone who knows a bit about linear congruential generators and modular arithmetic can find the reverse RNG sequence quite easily.

In those games, the RNG has a 32-bit state. Let S be the RNG state at a given instant. Then the next state will be S' = 1103515245 · S + 24691. The operations must be seen as in modular arithmetic modulo 2³², that is, if the result is 2³² or more, then 2³² is substracted to the result until the result is less than 2³². Then S' - 24691 = 1103515245 · S and (S' - 24691) · X = S · 1103515245 · X for all X. If X is such that 1103515245 · X = 1 in modular arithmetic modulo 2³² (so it is an integer such that 1103515245 · X = 1 - 2^32 · Y for some integer Y, or 1103515245 · X + 2^32 · Y = 1), then (S' - 24691) · X = S. The Bézout's identity guarantees that such an integer does exist.

The extended Euclidean Algorithm can be used to get X and Y by using 2³² and 1103515245 as inputs. You get X = -289805467, Y = 74460346, so 1103515245 · (-289805467) + 2^32 · 74460346 = 1. -289805467 is equivalent to 2³² - 289805467 = 4005161829.

So the reverse RNG sequence is S = (S' - 24691) · 4005161829 (you can also write that S = S' · 4005161829 - 24691 · 4005161829, but you do not need to calculate 24691 · 4005161829). Now you can search for a PID matching some IVs by exploring the states that give out the wanted Special Attack, Special Defense and Speed IVs (which, if you want the exact IVs, are only 2 times 65536), generate the random numbers backwards and check if the numbers fulfill the wanted conditions.

What is the point of making a tool for those old games?

What is the point of playing any newer Pokémon game, providing that they do not have the Trick House?

Omega Ruby and Alpha Sapphire do have the Trick House!

You got me.