Pocklington's algorithm
Pocklington's algorithm is a technique for solving a congruence of the form where "x" and "a" are integers and "a" is a quadratic residue. The algorithm is one of the first efficient methods to solve such a congruence. It was described by H.C. Pocklington in 1917. The algorithm. Inputs: Outputs: Solution method. Pocklington separates 3 different cases for "p": The first case, if formula_7, with formula_8, the solution is formula_9. The second case, if formula_10, with formula_8 and The third case, if formula_21, put formula_22, so the equation to solve becomes formula_23. Now find by trial  and error formula_24 and formula_25 so that formula_26 is a quadratic non-residue. Furthermore, let The following equalities now hold: Supposing that "p" is of the form formula_29 (which is true if "p" is of the form formula_30), "D" is a quadratic residue and formula_31. Now the equations give a solution formula_33. Let formula_34. Then formula_35. This means that either formula_36 or formula_37 is divisible by "p". If it is formula_37, put formula_39 and proceed similarly with formula_40. Not every formula_41 is divisible by "p", for formula_25 is not. The case formula_43 with "m" odd is impossible, because formula_44 holds  and this would mean that formula_45 is congruent to a quadratic non-residue, which is a contradiction. So this loop stops when formula_46 for a particular "l". This gives formula_47, and because formula_48 is a quadratic residue, "l" must be even. Put formula_49. Then formula_50. So the solution of formula_23 is got by solving the linear congruence formula_52. Examples. The following are 4 examples, corresponding to the 3 different cases in which Pocklington divided forms of "p". All formula_2 are taken with the modulus in the example. Example 0. This is the first case, according to the algorithm, formula_55, but  then formula_56 not 43, so we should not apply the algorithm at all. The reason why the algorithm is not applicable is that a=43 is a quadratic non residue for p=47. Example 1. Solve the congruence The modulus is 23. This is formula_58, so formula_59. The solution should be formula_60, which is indeed true: formula_61. Example 2. Solve the congruence The modulus is 13. This is formula_63, so formula_64. Now verifying formula_65. So the solution is formula_66. This is indeed true: formula_67. Example 3. Solve the congruence formula_68. For this, write formula_69. First find a formula_24 and formula_25 such that  formula_72 is a quadratic nonresidue. Take for example formula_73. Now find formula_74, formula_75 by computing And similarly formula_78 such that formula_79 Since formula_80, the equation formula_81 which leads to solving the equation formula_82. This has solution formula_83. Indeed, formula_84.