1  # Pell Equation Solver written in Rust
  2  
  3  This Rust project provides a command-line tool to solve Pell's equation, a classical problem in number theory. The program can be run in both interactive and non-interactive modes, allowing users to find solutions to the equation x² - n·y² = 1 for a given non-square integer `n`.
  4  
  5  ![GUI and QR code Image](images/pell.svg)
  6  
  7  ## Table of Contents
  8  
  9  - [What is Pell's Equation?](#what-is-pells-equation)
 10  - [How to Solve Pell's Equation](#how-to-solve-pells-equation)
 11  - [Features](#features)
 12  - [Installation](#installation)
 13  - [Usage](#usage)
 14  - [Examples](#examples)
 15  - [Testing](#testing)
 16  - [Contact](#contact)
 17  - [Acknowledgements](#acknowledgements)
 18  ## What is Pell's Equation?
 19  
 20  Pell's equation is a Diophantine equation of the form:
 21  
 22  x² - n·y² = 1
 23  
 24  where:
 25  
 26  - `x` and `y` are integers,
 27  - `n` is a positive non-square integer.
 28  
 29  The equation is named after the 17th-century mathematician John Pell, although it was first studied extensively by Brahmagupta and later by Euler. Pell's equation has infinitely many solutions if `n` is not a perfect square. The smallest non-trivial solution (x₁, y₁) is called the **fundamental solution**, and all other solutions can be generated from it.
 30  
 31  ## How to Solve Pell's Equation
 32  
 33  The standard method to solve Pell's equation involves the following steps:
 34  
 35  1. **Continued Fraction Expansion**: Compute the continued fraction expansion of √n. The expansion will eventually become periodic, and the period helps in finding the fundamental solution.
 36  
 37  2. **Convergents**: Compute the convergents of the continued fraction. These are rational approximations to √n, and one of them will yield the fundamental solution (x₁, y₁).
 38  
 39  3. **Generating Solutions**: Once the fundamental solution is found, all other solutions can be generated using the recurrence relation:
 40  
 41  xₖ₊₁ = x₁·xₖ + n·y₁·yₖ
 42  
 43  yₖ₊₁ = x₁·yₖ + y₁·xₖ
 44  
 45  
 46  This project implements these steps efficiently using Rust's powerful numerical libraries.
 47  
 48  ## Features
 49  
 50  - **Interactive Mode**: Run the program interactively to input values and see solutions.
 51  - **Command-Line Mode**: Pass arguments directly to the program for quick solutions.
 52  - **Efficient Computation**: Uses Rust's `num-bigint` library for handling large integers.
 53  - **Customizable Solution Count**: Specify how many solutions you want to generate.
 54  
 55  ## Installation
 56  
 57  To use this tool, you need to have Rust installed on your system. If you don't have Rust installed, you can install it from [rustup.rs](https://rustup.rs/).
 58  
 59  1. Clone the repository:
 60  
 61  Using Radicle 
 62  
 63  ```bash
 64  rad clone rad:z33QL2oAB9iszdd8tHZtCyuV4S6Fi
 65  ```
 66  
 67  Using Git
 68  
 69  ```bash 
 70  git clone https://seed.radicle.garden/z33QL2oAB9iszdd8tHZtCyuV4S6Fi.git PES
 71  ```
 72  
 73  2. Build the project:
 74  
 75  ```bash
 76  cargo build --release
 77  ```
 78  
 79  3. Run the program:
 80  
 81  ```bash
 82  ./pes
 83  ```
 84  
 85  ## Usage
 86  
 87  Interactive Mode
 88  Run the program without arguments to enter interactive mode:
 89  
 90  ```bash
 91  ./pes
 92  ```
 93  You will be prompted to enter a non-square integer n and the number of solutions you want to find.
 94  
 95  Command-Line Mode
 96  You can also run the program with command-line arguments:
 97  
 98  ```bash
 99  ./pes 7 -c 10
100  ```
101  <n>: The value of n in the Pell equation x² - n·y² = 1.
102  
103  -c <count>: (Optional) The number of solutions to find. Default is 5.
104  
105  
106  ## Examples
107  
108  1. Find the fundamental solution for n = 92:
109  
110  ```bash
111  ./pes 92 -c 10
112  ```
113  Output:
114  
115  ```bash
116  Pell equation solver: x² - 92·y² = 1
117  Finding solutions...
118  
119  Fundamental solution (x, y) = (1151, 120)
120  Generating additional solutions...
121  
122  Solutions to x² - 92·y² = 1:
123  Solution 1: (x, y) = (1151, 120)
124  Solution 2: (x, y) = (2649601, 276240)
125  Solution 3: (x, y) = (6099380351, 635904360)
126  Solution 4: (x, y) = (14040770918401, 1463851560480)
127  Solution 5: (x, y) = (32321848554778751, 3369785656320600)
128  Solution 6: (x, y) = (74404881332329766401, 7757245116998460720)
129  Solution 7: (x, y) = (171280004505174567476351, 17857174889544800256840)
130  Solution 8: (x, y) = (394286495966030522000793601, 41107208838487013192784960)
131  Solution 9: (x, y) = (907647342433797756471259393151, 94628776889022214824990721080)
132  Solution 10: (x, y) = (2089403787996106469366317122240001, 217835403291320300040115447141200)
133  
134  ```
135  
136  ## Testing
137  
138  The project includes unit tests to ensure correctness. You can run the tests using:
139  
140  ```bash
141  cargo test
142  ```
143  
144  Output:
145  
146  ```bash
147  Compiling pes v0.1.0 (/home/h4ck8r/Desktop/my_rust_dossier/pes)
148      Finished `test` profile [unoptimized + debuginfo] target(s) in 25.96s
149       Running unittests src/main.rs (target/debug/deps/pes-64c99cdd23c266b2)
150  
151  running 4 tests
152  test tests::test_continued_fraction_sqrt ... ok
153  test tests::test_find_pell_solutions ... ok
154  test tests::test_generate_more_solutions ... ok
155  test tests::test_is_pell_solution ... ok
156  
157  test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
158  ```
159  
160  
161  ## Contact
162  
163  For encrypted email correspondence, please refer to the file public-key.asc.
164  
165  ## Official Website
166  
167  https://enkryp.duckdns.org
168  
169  ## e-mail
170  
171  battosai@dnmx.su
172  
173  ## LXMF Address 
174  
175  1b634f9ac2aee34bec3276ad17f52d11
176  
177  An LXMF address is a unique identifier used for secure communication over the LXMF protocol, enabling users to send and receive encrypted messages. I suggest using the Sideband app or Nomad Network for this purpose.
178  
179  ## Briar
180  
181  To connect via Briar, please first add me using the link provided, and then send your Briar link to my email. I will promptly add you to my trusted contacts.
182  
183  briar://ac4jkk7rqcb7vbvjudzvoav64lcypoo3qaj3b5wnndcvvsdpz3fvs
184  
185  ## Acknowledgements
186  
187  I would like to express my deepest gratitude to my friends at #hackfreedom, whose unwavering encouragement and inspiration have been instrumental in the creation of this code. To the Cynics who question everything, the Abstract minds that see patterns where others see noise, and the Crispies who always keep things sharp — thank you. To the Foxes, cunning as ever, and the Lords of Skull and shadow — your support has been invaluable. And finally, to the one whose presence always leaves an effect — et qui comprend ces mots sans effort — you know who you are.
188  
189  This code began with a simple question — a Pell equation — cast into the noisy void of the chat. Most of it was met with confusion, ignorance, and the sound of braying from those who contribute nothing but emptiness. While they fumbled with nonsense, my friends stood apart — understanding, encouraging, and offering insight where others offered only noise. This work stands as proof that even the most complex ciphers are no match for true friendship — and that intelligence, much like cryptography, thrives in the presence of the right keys.
190