NonLinear Feedback Shift Registers (NLFSRs) are key primitives to design pseudorandom generators in modern stream ciphers and random sequence generation especially when the feedback function is of low degree which are of high interest for hardware implementation. Finding a systematic procedure of acceptable complexity for constructing NLFSRs with maximum period is still a general open problem and only a few results have been obtained so far. In this paper, we present the final results of an exhaustive exploratory search and analysis of NLFSRs of low degree of the form \(\sum _{i = 0}^{n - 1}c_i.x^i + x^n + x_j.x_k\) initiated in [11]. We first eliminate all polynomials producing short cycles very easily with a systematic approach. Then by modelling NLFSRs as graphs and considering the associated formal incidence matrix we express the maximum period property as graph properties. From them, we can generate equations (constraints) to be satisfied. This two-step approach enables to reduce the number of possible candidates greatly. They can then be tested finally for the maximum period property by HPC on GPGPUs and Massively Parallel Processor Array (MPPA). From those results, we have already identified new properties that should help to reduce the initial step further.